Unlocking the Secret Chambers

In a recent archaeological discovery at the Qin Terracotta Warriors' tomb pit, several secret chambers were uncovered. Each chamber is secured by a peculiar door that features multiple rotating dials. The i^th door has (a_i) dials. The j^th dial on the door is evenly divided into (b_{i,j}) sectors which are numbered (0, 1, \dots, b_{i,j}-1) in clockwise order. A pointer on every dial advances by one sector (modulo (b_{i,j})) roughly every 1.53 seconds. The door will open when all pointers simultaneously point to sector (0).

However, when these chambers were discovered, the pointers on the dials were not aligned to (0) (in fact, each pointer was at a different number). According to the mechanism, there are cases where the door will never open. Given the current state of the dials, your task is to determine whether it is possible for the door to eventually open.

Formally, for a given door with (n) dials, the (j^th) dial has (b_j) sectors and its pointer is currently at position (p_j) (with (0 \le p_j < b_j)). The dial advances by one every unit time. Thus, after (t) time units, the position of the pointer on the (j^th) dial will be ((p_j + t) \mod b_j). The door opens if and only if there exists a non-negative integer (t) such that for every dial (j), ((p_j + t) \mod b_j = 0).

This problem reduces to checking if there exists an integer (t) satisfying the system of congruences: [ \begin{aligned} t &\equiv -p_1 \pmod{b_1},\ t &\equiv -p_2 \pmod{b_2},\ &,\vdots\ t &\equiv -p_n \pmod{b_n}. \end{aligned} ] A necessary and sufficient condition for the existence of such a (t) is that for any two dials (i) and (j), [ (-p_i) \equiv (-p_j) \quad (\bmod; \gcd(b_i, b_j)). ] If this condition holds for all pairs, then the door can eventually be opened; otherwise, it cannot.

Your task is to determine, given the number of dials and for each dial the number of sectors and its current pointer position, whether the door can eventually open. Output "YES" if it is possible and "NO" otherwise.

inputFormat

The input begins with a single integer (T) representing the number of test cases. Each test case consists of three lines:

1. An integer (n) representing the number of dials on the door.
2. A line containing (n) space-separated integers, where the (j^th) integer (b_j) denotes the number of sectors on the (j^th) dial.
3. A line containing (n) space-separated integers, where the (j^th) integer (p_j) denotes the current pointer position on the (j^th) dial. It is guaranteed that (0 \le p_j < b_j) and initially the door is closed (i.e. not all (p_j) are zero).

For example:

5 2 3 4 1 2 2 4 6 1 3 2 6 8 1 4 3 3 5 7 1 2 3 1 5 3

outputFormat

For each test case, output a single line containing either "YES" if there exists a time (t \geq 0) such that the door will eventually open, or "NO" if it is impossible.

sample

5
2
3 4
1 2
2
4 6
1 3
2
6 8
1 4
3
3 5 7
1 2 3
1
5
3

YES
YES
NO
YES
YES