Adding On Segments SOLUTION ADDONSEG

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.

Watermelon SOLUTION WATMELON

GCD operations SOLUTION GCDOPS

Root the Tree SOLUTION ROOTTREE

Robot Detector SOLUTION UKROBOT

Permutation Split SOLUTION PERMSPL

Few Different Elements SOLUTION FEWDIFF

Adding on Segments SOLUTION ADDONSEG

March Long Challenge 2021 Solutions

An Interesting Sequence ISS SOLUTION
Tree House THOUSES SOLUTION
Valid Paths VPATH SOLUTION
Modular Equation MODEQ SOLUTION
Tic Tac Toe TCTCTOE SOLUTION
Xor Equality XOREQUAL SOLUTION
Golf LKDNGOLF SOLUTION
Solubility SOLBLTY SOLUTION

April Long Challenge 2021 Solutions

Chef and Dice SDICE Solution
Worthy Matrix KAVGMAT Solution
Binary String MEX MEXSTR Solution
Boolean Game BOOLGAME Solution
Tree Permutations TREEPERM Solution
Destroy the EMP Chip CHAOSEMP Solution
Chef and Pair Flips PAIRFLIP Solution
String Power STRPOW Solution
Brahma and Shiva SHRINES Solution
Water Sort Puzzle (Challenge) WTRSORT Solution
World Record BOLT Solution
Strong Language SSCRIPT Solution
Valid Pair SOCKS1 Solution

Adding on Segments SOLUTION ADDONSEG