Background

Statistics is an old and fascinating subject.

It is said that many years ago, a god named Huipu came to Earth and discovered humans, another intelligent species.

Hack testdata has been added in Subtask 5 and is not scored.

Problem Description

A sequence $\{a_n\}$ is defined to be partition-averagable if and only if there exists a partition $S_1,S_2,\cdots,S_k$ of $\{1,2,\cdots,n\}$ (where $k>1$) such that for every integer $1\le i\le k$, the average of the elements in sequence $\{a\}$ whose indices are in $S_i$ are all the same integer.

Now, given the sequence $\{a_n\}$, determine whether it is partition-averagable.

If some definitions are not very clear to you, you can refer to the “Hint” section at the end.

Input Format

The first line contains a positive integer $q$, which represents the number of queries.

For each query, the first line contains a positive integer $n$, describing the length of the sequence. The second line contains $n$ integers, representing the sequence $\{a_n\}$.

Output Format

Output $q$ lines. For each query, if the sequence is partition-averagable, output Yes; otherwise, output No.

4
5
1 1 1 1 1
5
1 2 3 4 5
5
1 1 1 1 6
5
-1 0 1 0 1

Yes
Yes
No
No

Hint

Hint

A partition of a set $S$ is defined as a collection of sets $U_1,U_2,\cdots,U_k$, satisfying:

• For all $i\neq j$, $U_i\cap U_j=\varnothing$.
• $U_1\cup U_2\cup\cdots\cup U_k=S$.

The average of a sequence $\{x_n\}$ is defined as:

$$\bar x=\dfrac{x_1+x_2+\cdots+x_n}{n}=\dfrac 1n\sum_{i=1}^nx_i$$

Sample Explanation

One possible partition for the first group of testdata: $\{1\},\{2\},\{3\},\{4\},\{5\}$.

One possible partition for the second group of testdata: $\{1,5\},\{2,4\},\{3\}$.

Note: the sets provided in a partition are sets of indices.

Constraints

This problem uses bundled testdata and subtask dependencies.

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{Score} & \textbf{Special Property}&\textbf{Dependent Subtasks}\\\hline \textsf{1} & 10 & 5 & \\\hline \textsf{2} & 10^3 & 20 & \sum a_i=0 \\\hline \textsf{3} & 100 & 25 & & \sf1\\\hline \textsf{4} & 10^3 & 50 & & \sf1\texttt{,}\ 3\\\hline \end{array}$$

For all testdata, $1\le q\le 10$, $2\le n\le 10^3$, $|a_i|\le 5\times10^3$.

Translated by ChatGPT 5