Array Differentiation solution codeforces

Array Differentiation solution codeforces



You are given a sequence of nn integers a1,a2,,ana1,a2,…,an.

Does there exist a sequence of nn integers b1,b2,,bnb1,b2,…,bn such that the following property holds?

  • For each 1in1≤i≤n, there exist two (not necessarily distinct) indices jj and kk (1j,kn1≤j,k≤n) such that ai=bjbkai=bj−bk.
Input

The first line contains a single integer tt (1t201≤t≤20) — the number of test cases. Then tt test cases follow.

The first line of each test case contains one integer nn (1n101≤n≤10).

The second line of each test case contains the nn integers a1,,ana1,…,an (105ai105−105≤ai≤105).

Output

For each test case, output a line containing YES if a sequence b1,,bnb1,…,bn satisfying the required property exists, and NO otherwise.

Example

input

Copy
5
5
4 -7 -1 5 10
1
0
3
1 10 100
4
-3 2 10 2
9
25 -171 250 174 152 242 100 -205 -258

output

Copy
YES
YES
NO
YES
YES
Note

In the first test case, the sequence b=[9,2,1,3,2]b=[−9,2,1,3,−2] satisfies the property. Indeed, the following holds:

  • a1=4=2(2)=b2b5a1=4=2−(−2)=b2−b5;
  • a2=7=9(2)=b1b5a2=−7=−9−(−2)=b1−b5;
  • a3=1=12=b3b2a3=−1=1−2=b3−b2;
  • a4=5=3(2)=b4b5a4=5=3−(−2)=b4−b5;
  • a5=10=1(9)=b3b1a5=10=1−(−9)=b3−b1.

In the second test case, it is sufficient to choose b=[0]b=[0], since a1=0=00=b1b1a1=0=0−0=b1−b1.

In the third test case, it is possible to show that no sequence bb of length 33 satisfies the property.



Also read : What a Reversal solution codeforces

Leave a Comment