Adding on Segments SOLUTION ADDONSEG

There are N integers A1,A2,…,AN on a circle. For each valid i, Ai and Ai+1 are adjacent; A1 and AN are also adjacent.

Chef has a sequence of integers B1,B2,…,BN, which he may use to perform any number of operations (including zero). In one operation, he should do the following:

Choose an integer i (1≤i≤N).

Choose i consecutive integers on the circle.

Choose a sign S=±1 and add S⋅Bi to each of the chosen integers. In other words, either add Bi to each of them or subtract Bi from each of them.

The goal is to make all the integers on the circle equal to 0. Can Chef achieve it using these operations?

Input

The first line of the input contains a single 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.

The second line contains N space-separated integers A1,A2,…,AN.

The third line contains N space-separated integers B1,B2,…,BN.

Output

For each test case, print a single line containing the string “YES” if it is possible to make all integers on the circle equal to 0 or “NO” if it is impossible.

Constraints

1≤N≤103

0≤Ai,Bi≤104 for each valid i

the sum of N over all test cases does not exceed 104

Subtasks

Subtask #1 (40 points): A1=A2=…=AN

Subtask #2 (60 points): original constraints

Example Input

1 1 3 3 2

0 0 2 1 0

1 1 1 1

2 2 2 2

2 0 1

0 3 5

Example Output

YES

Explanation

Example case 1: We can make everything 0 using two operations: choose i=4 and change the circular sequence (1,1,3,3,2) to (1−1,1−1,3−1,3−1,2)=(0,0,2,2,2), then choose i=3 and change it to (0,0,2−2,2−2,2−2)=(0,0,0,0,0).

Example case 2: The parities of integers on the circle cannot change, so they cannot become 0.