310537: CF1848C. Vika and Price Tags

C. Vika and Price Tagstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vika came to her favorite cosmetics store "Golden Pear". She noticed that the prices of $n$ items have changed since her last visit.

She decided to analyze how much the prices have changed and calculated the difference between the old and new prices for each of the $n$ items.

Vika enjoyed calculating the price differences and decided to continue this process.

Let the old prices be represented as an array of non-negative integers $a$, and the new prices as an array of non-negative integers $b$. Both arrays have the same length $n$.

In one operation, Vika constructs a new array $c$ according to the following principle: $c_i = |a_i - b_i|$. Then, array $c$ renamed into array $b$, and array $b$ renamed into array $a$ at the same time, after which Vika repeats the operation with them.

For example, if $a = [1, 2, 3, 4, 5, 6, 7]$; $b = [7, 6, 5, 4, 3, 2, 1]$, then $c = [6, 4, 2, 0, 2, 4, 6]$. Then, $a = [7, 6, 5, 4, 3, 2, 1]$; $b = [6, 4, 2, 0, 2, 4, 6]$.

Vika decided to call a pair of arrays $a$, $b$ dull if after some number of such operations all elements of array $a$ become zeros.

Output "YES" if the original pair of arrays is dull, and "NO" otherwise.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of items whose prices have changed.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the old prices of the items.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le 10^9$) — the new prices of the items.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output "YES" if the pair of price arrays is dull, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

ExampleInput

9
4
0 0 0 0
1 2 3 4
3
1 2 3
1 2 3
2
1 2
2 1
6
100 23 53 11 56 32
1245 31 12 6 6 6
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
3
4 0 2
4 0 2
3
2 5 2
1 3 4
2
6 1
4 2
2
0 0
0 3

Output

YES
YES
NO
NO
YES
YES
NO
YES
YES

Note

In the first test case, the array $a$ is initially zero.

In the second test case, after the first operation $a = [1, 2, 3], b = [0, 0, 0]$. After the second operation $a = [0, 0, 0], b = [1, 2, 3]$.

In the third test case, it can be shown that the array $a$ will never become zero.

题目大意：
维卡来到她最喜欢的化妆品店“金梨”。她注意到自从上次来访以来，n件商品的价格已经发生了变化。她决定分析价格变化了多少，并计算了每件n商品的旧价格和新价格之间的差异。维卡喜欢计算价格差异，并决定继续这个过程。

设旧价格为非负整数数组a，新价格为非负整数数组b。两个数组的长度都是n。在一次操作中，维卡根据以下原则构建一个新数组c：ci = |ai - bi|。然后，数组c重命名为数组b，数组b重命名为数组a，之后维卡再对它们进行操作。

如果经过一些操作后，数组a的所有元素都变为零，维卡决定称数组对a，b为“乏味”。

如果原始数组对是乏味的，输出“YES”，否则输出“NO”。

输入输出数据格式：
每个测试用例包含多个测试案例。第一行包含一个整数t（1≤t≤10^4）——测试案例的数量。测试案例的描述如下。

每个测试案例的第一行包含一个整数n（1≤n≤10^5）——价格变化的商品数量。

第二行包含n个整数a1，a2，…，an（0≤ai≤10^9）——商品的老价格。

第三行包含n个整数b1，b2，…，bn（0≤bi≤10^9）——商品的新价格。

保证所有测试案例的n之和不超过10^5。

对于每个测试案例，如果价格数组对是乏味的，输出“YES”，否则输出“NO”。

示例输入输出：
输入：
9
4
0 0 0 0
1 2 3 4
3
1 2 3
1 2 3
2
1 2
2 1
6
100 23 53 11 56 32
1245 31 12 6 6 6
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
3
4 0 2
4 0 2
3
2 5 2
1 3 4
2
6 1
4 2
2
0 0
0 3

输出：
YES
YES
NO
NO
YES
YES
NO
YES
YES

注意：
在第一个测试案例中，数组a最初为零。

在第二个测试案例中，第一次操作后a = [1, 2, 3], b = [0, 0, 0]。第二次操作后a = [0, 0, 0], b = [1, 2, 3]。

在第三个测试案例中，可以证明数组a永远不会变为零。题目大意： 维卡来到她最喜欢的化妆品店“金梨”。她注意到自从上次来访以来，n件商品的价格已经发生了变化。她决定分析价格变化了多少，并计算了每件n商品的旧价格和新价格之间的差异。维卡喜欢计算价格差异，并决定继续这个过程。 设旧价格为非负整数数组a，新价格为非负整数数组b。两个数组的长度都是n。在一次操作中，维卡根据以下原则构建一个新数组c：ci = |ai - bi|。然后，数组c重命名为数组b，数组b重命名为数组a，之后维卡再对它们进行操作。 如果经过一些操作后，数组a的所有元素都变为零，维卡决定称数组对a，b为“乏味”。 如果原始数组对是乏味的，输出“YES”，否则输出“NO”。 输入输出数据格式： 每个测试用例包含多个测试案例。第一行包含一个整数t（1≤t≤10^4）——测试案例的数量。测试案例的描述如下。 每个测试案例的第一行包含一个整数n（1≤n≤10^5）——价格变化的商品数量。 第二行包含n个整数a1，a2，…，an（0≤ai≤10^9）——商品的老价格。 第三行包含n个整数b1，b2，…，bn（0≤bi≤10^9）——商品的新价格。 保证所有测试案例的n之和不超过10^5。 对于每个测试案例，如果价格数组对是乏味的，输出“YES”，否则输出“NO”。 示例输入输出： 输入： 9 4 0 0 0 0 1 2 3 4 3 1 2 3 1 2 3 2 1 2 2 1 6 100 23 53 11 56 32 1245 31 12 6 6 6 7 1 2 3 4 5 6 7 7 6 5 4 3 2 1 3 4 0 2 4 0 2 3 2 5 2 1 3 4 2 6 1 4 2 2 0 0 0 3 输出： YES YES NO NO YES YES NO YES YES 注意： 在第一个测试案例中，数组a最初为零。 在第二个测试案例中，第一次操作后a = [1, 2, 3], b = [0, 0, 0]。第二次操作后a = [0, 0, 0], b = [1, 2, 3]。 在第三个测试案例中，可以证明数组a永远不会变为零。