NITK06 - MODIFY SEQUENCE


Suppose we have a sequence of non-negative integers, Namely a1, a2, ..., an. At each time we can choose one term ai with 0 < i < n and we subtract 1 from both ai and ai+1. We wonder whether we can get a sequence of all zeros after several operations.

Input

The first line is the number of test cases T (0 < T <= 20).

The first line of each test case is a number N (0 < N <= 10000). The next line is N non-negative integers, 0 <= ai <= 109.

Output

If it can be modified into all zeros with several operations output “YES” in a single line, otherwise output “NO” instead.

Example

Input:
2
2
1 2
2
2 2

Output:
NO
YES

Explanation

It is clear that [1 2] can be reduced to [0 1] but no further to convert all integers to 0. Hence, the output is NO.

In second case, output is YES as [2 2] can be reduced to [1 1] and then to [0 0] in just two steps.


hide comments
Vars: 2015-08-07 05:40:23

easy one...need to observe pattern thats it :)

rk: 2015-06-29 15:31:59

nice adhoc ques.

:.Mohib.:: 2015-02-23 15:13:06

nice...

Ankit Jain: 2013-12-01 19:04:17

easy and nice..there should be more such probs on spoj..

Raushan Kumar: 2013-11-04 15:21:22

good problem


Added by:Gaurav Jain
Date:2013-09-25
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64