Petya and Sequence

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Little Petya likes integer numbers a lot. Recently he has received a sequence of integers as a gift from his mother. Petya calls a sequence of N integers A_{i} beautiful if there exist a sequence of N integer numbers B_{i} for which the following conditions hold:
 At least one number B_{i} differs from 0.
 For every j from 0 to N1 the following holds:
A_{0}* B_{j} + A_{1}* B_{(j + 1) mod N} + ... + A_{N1}* B_{(j + N  1) mod N} = 0.
Please, help Petya to check if his sequence A_{i} is beautiful.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in Petya's sequence. The second line contains N spaceseparated integers A_{0}, A_{1}, ..., A_{N1} denoting the sequence.
Output
For each test case, output a single line containing the word "YES"(without quotes) if Petya's sequence is beautiful and "NO", otherwise.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 3 * 10^{4}
 1000 ≤ A_{i} ≤ 1000
Sum of N for all test cases in a single input file will not exceed 150 000.
Example
Input: 4 3 1 0 0 3 1 1 1 4 2 4 1 1 5 1 3 2 1 5 Output: NO YES YES NO
Explanation
Example case 2. One of the possible sequences B is (1, 1, 0).
Example case 3. One of the possible sequences B is (1, 1, 1, 1).
Author:  KADR 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/REALSET 
Tags  KADR, dec13, fft, hard, maths 
Date Added:  18102013 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 