| DJC | Competitive Programming | Codeforces |

Contest 2131 - Codeforces - DJC

Link to the contest Here

A. Lever

Time limit per test: 2 seconds
Memory limit per test: 256 megabytes

In the Divergent Universe, The Lever iterates itself given two arrays a and b of length n.
In each iteration, The Lever will do the following:

Choose a random index i such that a[i] > b[i].
Then, decrease a[i] by 1.
If no such i exists, this step is skipped.
Choose a random index i such that a[i] < b[i].
Then, increase a[i] by 1.
If no such i exists, this step is skipped.

After each iteration, The Lever will check whether step 1 was skipped.
If it was, the iterations will stop.

You are given the two arrays. You must find the number of iterations that The Lever performs.
It can be proven that this number is fixed, regardless of the random choices The Lever makes at each step.

Input

Each test contains multiple test cases.

The first line contains an integer t — the number of test cases — (1 ≤ t ≤ 10^4).
The description of the test cases follows.

In each test case:

The first line contains an integer n (1 ≤ n ≤ 10).
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 10).
The third line contains n integers b1, b2, …, bn (1 ≤ bi ≤ 10).

Output

For each test case, print a single integer:
the number of iterations that The Lever performs.

Example

Input


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

Output

Note

In the first sample case:

Iteration 1: Decrease a1 by 1 and increase a2 by 1.
a goes from [7, 3] to [6, 4].
Iteration 2: Decrease a1 by 1 and increase a2 by 1.
a goes from [6, 4] to [5, 5].
Iteration 3: Increase a2 by 1.
a goes from [5, 5] to [5, 6].

Since in the third iteration no element could be decreased (step 1 skipped), the process stops.
Therefore, the answer is 3.

In the second sample case, The Lever makes no changes in the first iteration, so the number of iterations is 1.

(Solved) Lever

The solution can be found by summing the differences of a[i] - b[i] and adding 1:

#include<bits/stdc++.h>
using namespace std;

int solve(){
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    int ans=0;

    for(int i=0;i<n;i++)
        if(a[i]>b[i]) ans+= a[i]-b[i];
    return ans + 1;
}

int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
        cout<<solve()<<endl;
    return 0;
}

B. Alternating Series

Time limit per test: 2 seconds Memory limit per test: 256 megabytes

You are given an integer n. We call an array a of length n good if it satisfies:

For all 1 ≤ i < n, we have a[i] ⋅ a[i+1] < 0 (i.e., the product of adjacent elements is negative).
For every subarray of length at least 2, the sum of all its elements is positive*†.

Moreover, we say that a good array a of length n is better than another good array b of the same length if:

The sequence [|a₁|, |a₂|, …, |aₙ|] is lexicographically smaller‡ than [|b₁|, |b₂|, …, |bₙ|].
Here |z| denotes the absolute value of integer z.

Your task is to print a good array of length n that is better than any other good array of length n.

An array c is a subarray of an array d if it can be obtained by removing several (possibly none or all) elements from the beginning and several (possibly none or all) elements from the end.

† An integer x is positive if x > 0.

‡ A sequence a is lexicographically smaller than a sequence b if and only if one of the following holds:

a is a prefix of b, but a ≠ b; or
At the first position where a and b differ, sequence a has an element smaller than the corresponding element in b.

Input

The first line contains an integer t (1 ≤ t ≤ 500) — the number of test cases.
Each test case contains one line with an integer n (2 ≤ n ≤ 2·10⁵) — the length of the array.

It is guaranteed that the sum of all n across the input does not exceed 2·10⁵.

Output

For each test case, print n integers a₁, a₂, …, aₙ (−10⁹ ≤ aᵢ ≤ 10⁹), the elements of the array, in a new line.

Example

Input

2
2
3

Output

-1 2
-1 3 -1

Note

In the first sample case:

a₁ ⋅ a₂ = −2 < 0 and a₁ + a₂ = 1 > 0, so it satisfies both conditions.
Moreover, it can be shown that the corresponding array b = [1, 2] is better than any other good array of length 2.

C. Make it Equal

Time limit per test: 2 seconds Memory limit per test: 256 megabytes

You are given two multisets S and T of size n and a positive integer k. You can perform the following operation any number of times (including zero) on S:

Select an element x in S and remove one occurrence of x from S.
Then, insert into S one of the following values:
x + k
|x − k| (the absolute value of x − k).

The goal is to determine whether it is possible to transform S into T. Two multisets S and T are equal if each element appears the same number of times in both.

Input

Each test contains multiple test cases.

The first line contains an integer t (1 ≤ t ≤ 10⁴) — the number of test cases.
The first line of each test case contains two integers n and k (1 ≤ n ≤ 2·10⁵, 1 ≤ k ≤ 10⁹): the size of S and the constant k, respectively.
The second line contains n integers S₁, S₂, …, Sₙ (0 ≤ Sᵢ ≤ 10⁹) — the elements of S.
The third line contains n integers T₁, T₂, …, Tₙ (0 ≤ Tᵢ ≤ 10⁹) — the elements of T.

It is guaranteed that the total sum of n across all test cases does not exceed 2·10⁵.

Output

For each test case, print "YES" if it is possible to make S equal to T, and "NO" otherwise.

The answer may be printed in any combination of uppercase and lowercase letters. For example: "yEs", "yes", "Yes", and "YES" are all considered positive answers.

Example

Input

Output

YES
YES
YES
NO
NO

Note

In the first case, we can remove the 1 from S and insert |1 − k| = |1 − 3| = 2, making S equal to T.
In the second case, we can remove the 4 from S and insert 4 + k = 4 + 8 = 12, making S equal to T.
In the last case, it can be proven that it is impossible to make S equal to T.

D. Alboris Contractio

Time limit per test: 2 seconds Memory limit per test: 256 megabytes

Kagari is preparing to archive a tree, and she knows that the cost will depend on its diameter∗. To reduce expenses, her goal is to decrease the diameter as much as possible first. She can perform the following operation on the tree:

Choose two vertices s and t.
Let the sequence of vertices in the simple path† from s to t be: v₀, v₁, …, vₖ, where v₀ = s and vₖ = t.
Delete all edges along the path, i.e., (v₀, v₁), (v₁, v₂), …, (vₖ₋₁, vₖ).
Connect the vertices v₁, v₂, …, vₖ directly to v₀, i.e., add edges (v₀, v₁), (v₀, v₂), …, (v₀, vₖ).

It can be proven that the graph remains a tree after this operation.

Help her determine the minimum number of operations required to achieve the minimum diameter.

∗ The diameter of a tree is the greatest possible distance between any pair of vertices. The distance is measured as the number of edges in the unique simple path connecting them.

† A simple path is one that does not visit any vertex more than once. In a tree, there always exists a unique simple path between two vertices.

Input

Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 10⁴), the number of test cases.

The description of each test case is as follows:

The first line of each test case contains an integer n (2 ≤ n ≤ 2·10⁵), the number of vertices of the tree.
The next n − 1 lines describe the edges. Each line contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), indicating that there is an edge between u and v.

It is guaranteed that the edges form a tree. It is also guaranteed that the total sum of n across all test cases does not exceed 2·10⁵.

Output

For each test case, print a single integer: the minimum number of operations required to minimize the diameter.

Example

Input

Output

Note

In the first case, the initial diameter is 3. Kagari can choose s = 3 and t = 4 and perform:

Remove (3,1), (1,2), and (2,4).
Add (3,1), (3,2), and (3,4).

The diameter is reduced to 2, which is the minimum possible.

In the second case, the diameter is 1, which is already minimal, so no operations are needed.

E. Adjacent XOR

Time limit per test: 2 seconds Memory limit per test: 256 megabytes

You are given an array a of length n. For each index i such that 1 ≤ i < n, you can perform the following operation at most once:

a[i] := a[i] ⊕ a[i+1]

where ⊕ denotes the bitwise XOR operation.

You can choose the indices and perform the operations in any sequential order.

Given another array b of length n, determine whether it is possible to transform a into b.

Input

Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 10⁴), the number of test cases.

The description of each test case is as follows:

The first line contains an integer n (2 ≤ n ≤ 2·10⁵).
The second line contains n integers a₁, a₂, …, aₙ (0 ≤ aᵢ < 2³⁰).
The third line contains n integers b₁, b₂, …, bₙ (0 ≤ bᵢ < 2³⁰).

It is guaranteed that the total sum of n across all test cases does not exceed 2·10⁵.

Output

For each test case, print "YES" if it is possible to transform a into b; otherwise, print "NO". The answer may be printed in any combination of uppercase and lowercase letters.

Example

Input

7
5
1 2 3 4 5
3 2 7 1 5
3
0 0 1
1 0 1
3
0 0 1
0 0 0
4
0 0 1 2
1 3 3 2
6
1 1 4 5 1 4
0 5 4 5 5 4
3
0 1 2
2 3 2
2
10 10
11 10

Output

YES
NO
NO
NO
YES
NO
NO

Note

In the first case, you can perform the operations in the following order:

Choose i = 3 and assign a₃ := a₃ ⊕ a₄ = 7, then a = [1, 2, 7, 4, 5].
Choose i = 4 and assign a₄ := a₄ ⊕ a₅ = 1, then a = [1, 2, 7, 1, 5].
Choose i = 1 and assign a₁ := a₁ ⊕ a₂ = 3, then a = [3, 2, 7, 1, 5].

F. Unjust Binary Life

Yuri has two binary strings a and b, both of length n. These two strings dynamically define an n × n grid. Let (i, j) be the cell at row i and column j. The initial value of cell (i, j) is a_i ⊕ b_j, where ⊕ denotes the bitwise XOR operation.

Yuri’s journey always starts at cell (1, 1). From a cell (i, j), she can only move down (i+1, j) or right (i, j+1). Her journey is possible if there exists a valid path such that all cells in the path (including (1, 1)) have value 0.

Before starting, she can perform the following operation any number of times:

Choose an index 1 ≤ i ≤ n and flip the value of a_i or b_i (a 0 becomes 1 and a 1 becomes 0). The grid will update accordingly.

Let f(x, y) be the minimum number of operations required for Yuri to be able to reach cell (x, y). You must determine the sum of f(x, y) for all 1 ≤ x, y ≤ n.

Note: Each of these n² cases is

independent. That is, the operations performed to reach (x, y) are not carried over to the next case.

Input

Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 10⁴), the number of test cases.

The description of each test case is as follows:

The first line contains an integer n (1 ≤ n ≤ 2·10⁵).
The second line contains the binary string a of length n.
The third line contains the binary string b of length n.

It is guaranteed that the total sum of n across all test cases does not exceed 2·10⁵.

Output

For each test case, print a single integer: the value of the sum Σ f(x, y) over all 1 ≤ x, y ≤ n.

Example

Input

Output

4
12

G. Undoubtedly Lucky Numbers

You are given an array a of length n. For a non-negative integer x, define f(x) as the sum of all a_i such that a_i ≤ x. Formally:

f(x) = ∑ { a_i | a_i ≤ x }

Your task is to answer q queries. In each query, you are given an integer k. You must print the minimum non-negative integer x such that f(x) ≥ k.

Input

Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 10⁴), the number of test cases.

The description of each test case is as follows:

The first line contains two integers n and q (1 ≤ n, q ≤ 2·10⁵).
The second line contains n integers a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 10⁹).
The third line contains q integers k₁, k₂, …, k_q (1 ≤ kᵢ ≤ 10¹⁸).

It is guaranteed that the total sum of n and the total sum of q across all test cases do not exceed 2·10⁵.

Output

For each query, print a single integer — the minimum non-negative integer x such that f(x) ≥ k. If no such x exists, print −1.

Example

Input

Output

Note

In the first test case:

f(1) = 1, which is enough for k = 2.
f(2) = 3, which is enough for k = 3.
f(5) = 11, which is enough for k = 9.

H. Private Key

You are given an integer n. Construct an array a of length n with the following properties:

1 ≤ a_i ≤ 10⁹ for all i.
All a_i are pairwise distinct.
For all 1 ≤ i < n, the bitwise AND between a_i and a_{i+1} is greater than 0.

Input

Each test contains multiple test cases. The first line contains an integer t (1 ≤ t ≤ 10⁴), the number of test cases.

The description of each test case is as follows:

The first line contains an integer n (2 ≤ n ≤ 10⁵).

It is guaranteed that the total sum of n across all test cases does not exceed 10⁵.

Output

For each test case, print n integers a₁, a₂, …, aₙ. If there are multiple valid answers, print any.

Example

Input

2
4
3

Output

7 3 6 5
2 3 1

| DJC | Competitive Programming | Codeforces |

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search