Problem Description

You are given a cycle of length $n$. Initially, each position has value $0$, and the positions are numbered from $1$ to $n$. You are also given two sequences $a_i$ and $b_i$, both of length $n$. You may perform the following operation any number of times:

• Choose a point $i$, and add or subtract $b_i$ to the consecutive segment of length $i$ starting from position $i$ and going forward along the cycle.

Determine whether there exists a sequence of operations such that the value at every position on the cycle is exactly equal to $a_i$. If so, construct one. For each position, output the number of times you add $b_i$ minus the number of times you subtract $b_i$.

It is guaranteed that $\operatorname{lcm}(b_i)\le 10^9$.

If for some test case you can only determine whether a solution exists but cannot construct one, you may still obtain partial score for that test case. See Scoring for details.

Input Format

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains a positive integer $n$, the length of the cycle.

• The second line contains $n$ integers $a_i$, the target values.

• The third line contains $n$ positive integers $b_i$.

Output Format

For each test case:

• Output YES or NO on the first line, indicating your verdict.

• If a solution exists, output $n$ integers on the second line, representing your construction. You must ensure that every integer lies between $-10^{32}$ and $10^{32}$.

7
5
0 2 2 6 6
1 2 2 2 2
5
-6 -8 -6 21 -6
1 4 2 4 4
5
-2 10 16 0 0
6 6 1 2 2
5
22 14 -2 14 14
4 4 4 8 1
5
2 6 2 2 2
2 1 1 2 1
5
2 3 7 8 8
2 1 2 1 2
5
-5 1 4 -2 -2
1 4 1 1 1

YES
-2 0 2 2 -1 
NO
YES
0 2 2 -2 1 
YES
0 -2 -2 1 14 
YES
0 4 0 2 -2 
YES
0 1 3 2 0 
YES
-2 1 1 -2 -1 

Hint

Constraints

For all test cases, $1\le n,T,\sum n\le 10^6$, $0\le |a_i|\le 10^9$, $1\le b_i,\operatorname{lcm}(b_i)\le 10^9$.

• Special Property A: It is guaranteed that $T\le 10$, and if a solution exists, then there is always one where the number of additions or subtractions for every $b_i$ does not exceed $5$.

• Special Property B: It is guaranteed that there exists a nonnegative integer $k$ such that $n=2^k$.

• Special Property C: It is guaranteed that all $a_i$ are equal.

• Special Property D: It is guaranteed that $2\nmid n$.

Scoring

• If you correctly determine the existence of a solution for all test cases, you can obtain $40$ of the score for that test point. Note that if you can only determine existence, then for the test cases where a solution exists, you should still output a second line consisting of $n$ integers within the required range.

• If you correctly determine the existence of a solution for all test cases, and for every test case with a solution you also construct a valid one, you can obtain $60$ of the score for that test point.