OCPC 2024 Summer, Day 4: wuhudsm Contest
A. Explosive String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There's a $$$1 \times n$$$ grid. For a string $$$y$$$ of length $$$l$$$, a robot moves according to the following pattern.

  • Initially, the robot selects a cell as the starting point.
  • Then, in the $$$i$$$-th $$$(1 \leq i \leq l)$$$ move, if $$$y_i = \mathtt{L}$$$, the robot moves one cell to the left; if $$$y_i = \mathtt{R}$$$, it moves one cell to the right. If the robot moves out of bounds, it explodes.

You are given a possibly incomplete string $$$x$$$ of length $$$m$$$. Your task is to complete the string $$$x$$$ such that, regardless of which cell the robot selects as the starting point, it will always explode. If there's no such string, output "NO" instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 50$$$).

The second line of each test case contains a string $$$x_1x_2 \ldots x_{m}$$$ of length $$$m$$$ consisting of characters 'L', 'R' and '?'. If $$$x_i=\mathtt{?}$$$ ($$$1 \le i \le m$$$), it means you need to choose 'L' or 'R' as the value of $$$x_i$$$.

Output

For each test case, if there's no such string, output "NO" in a new line. Otherwise, output "YES" in a new line, then output the complete string $$$x$$$ in the next line.

Example
Input
4
1 1
L
2 1
?
3 5
LR?R?
50 5
?????
Output
YES
L
NO
YES
LRRRL
NO
Note

In the first test case, the robot can only choose the first cell as the start point. Then, in the first move, the robot moves one cell to the left, which is out of bounds. After the first move, the robot will explode, so the answer is "YES".

In the second test case, if $$$x=\mathtt{L}$$$, the robot can choose the second cell as the start point. If $$$x=\mathtt{R}$$$, the robot can choose the first cell as the start point. In both cases, the robot will not explode. Thus, the answer is "NO".

B. Doors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ doors. You want to open all of them. There are some rules.

At first, you can only open the first door. For each $$$i \ge 1$$$, you can open the $$$i+1$$$-th door only if you have already opened the $$$i$$$-th door.

Initially, you have $$$x$$$ coins. There is a lock on the $$$i$$$-th door with a cost of $$$c_i$$$. In other words, you need to spend $$$c_i$$$ coins to open the $$$i$$$-th door. If the number of coins you currently have is strictly less than $$$c_i$$$, you will not be able to open the $$$i$$$-th door. After opening the $$$i$$$-th door, you will receive $$$a_i$$$ coins as a prize.

You can do the following operation any number of times:

  • Choose an index $$$i$$$, where $$$1 \le i \le n$$$, and set $$$c_i$$$ to $$$0$$$.

Find the minimum number of operations necessary to open all the doors.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. For each test case:

  • The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le x \le 10^9$$$).
  • The second line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 10^9$$$).
  • The third line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output

For each test case, output the minimum number of operations needed to open all the doors.

Example
Input
3
1 1
1
1
3 10
9 6 5
1 1 1
3 10
5 9 9
1 2 9
Output
0
1
2
Note

In the first test case, you don't need to perform any operations. You can just spend $$$1$$$ coin to open the first (and only) lock.

In the second test case, you can first set $$$c_i$$$ to $$$0$$$. Then, you can do the following:

  • Open the first door. You spend $$$0$$$ coins and receive $$$1$$$ coin. After that, you have $$$11$$$ coins.
  • Open the second door. You spend $$$6$$$ coins and receive $$$1$$$ coin. After that, you have $$$6$$$ coins.
  • Open the third door. You spend $$$5$$$ coins and receive $$$1$$$ coin. After that, you have $$$2$$$ coins.

C. Minimum Inversions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ of length $$$n$$$. There is a sequence $$$b$$$ which is initially empty. You need to perform $$$n$$$ operations.

In the $$$i$$$-th operation, you can choose one of the following two types of operations:

  1. insert $$$a_i$$$ into the beginning of $$$b$$$;
  2. insert $$$a_i$$$ into the end of $$$b$$$.

Solve the following problem for each $$$j$$$, where $$$0 \le j \le n$$$: find the minimum possible number of inversions$$$^\dagger$$$ in $$$b$$$ if exactly $$$j$$$ operations of the first type are performed.

$$$^\dagger$$$ An inversion in a sequence is a pair of elements where the earlier element is greater than the later element. In other words, for a sequence $$$b$$$, a pair $$$(b_i, b_j)$$$ is an inversion only if $$$i \lt j$$$ and $$$b_i \gt b_j$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. For each test case:

  • The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$).
  • The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$).

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

Output

For each test case, output $$$n+1$$$ integers. The $$$j$$$-th integer should be the minimum possible number of inversions when exactly $$$j$$$ operations of the first type are performed, for $$$j=0,\ldots,n$$$.

Example
Input
3
2
2 1
5
3 2 4 1 2
6
3 2 6 1 5 4
Output
1 0 0
6 3 2 1 1 3
7 4 3 3 4 6 8
Note

Consider the first test case.

  • If $$$j = 0$$$, the only way is to do two operations of the second type. After that, $$$b=[2,1]$$$ and the number of inversions is $$$1$$$.
  • If $$$j = 1$$$, the optimal way is to perform an operation of the second type and then perform an operation of the first type. After that, $$$b=[1,2]$$$ and the number of inversions is $$$0$$$.
  • If $$$j = 2$$$, the only way is to do two operations of the first type. After that, $$$b=[1,2]$$$ and the number of inversions is $$$0$$$.

D. Breezy GCD Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ intervals $$$[l_i,r_i]$$$, where $$$l_i \le r_i$$$. Your task is to determine if there exist $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ satisfying:

  • $$$l_i\le x_i \le r_i$$$ for all $$$1 \le i \le n$$$;
  • $$$\operatorname{gcd}(x_1,x_2,\ldots,x_n) \neq 1$$$.
Here, $$$\operatorname{gcd}(x_1,x_2,\ldots,x_n)$$$ denotes the greatest common divisor of $$$x_1,x_2,\ldots,x_n$$$.
Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) denoting the number of intervals.
  • The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 10^6$$$).
  • The third line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \le r_i \le 10^6$$$).

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 it is possible to choose $$$x_1,x_2,\ldots,x_n$$$ such that it satisfies the constraints. On the next line, output $$$n$$$ space-separated integers $$$x_1,x_2,\ldots,x_n$$$.
  • NO otherwise.

The letters in the word YES and NO are case insensitive. For example, YES, yeS and No are all considered valid.

Example
Input
4
3
1 5 10
5 6 11
4
2 3 4 1000000
2 3 4 1000000
5
34 15 55 233 51
34 20 99 299 51
3
1 1 1
1 1 2
Output
YES
5 5 10
NO
YES
34 17 85 255 51
NO
Note

In the first example, we choose $$$5$$$, $$$5$$$ and $$$10$$$ respectively from each range. Then, we have $$$\operatorname{gcd}(5,5,10) = 5 \neq 1$$$.

In the second example, it is not possible to choose $$$n$$$ integers satisfying the condition.

E. Manhattan Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We call a tree with nodes numbered from $$$1$$$ to $$$n$$$ a Manhattan tree only if there exist $$$n$$$ points $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ in a two-dimensional plane such that for any $$$i, j$$$ ($$$1 \leq i \lt j \leq n$$$), the Manhattan distances$$$^*$$$ from $$$(x_i, y_i)$$$ to $$$(x_j, y_j)$$$ is equal to the distance$$$^\dagger$$$ between node $$$i$$$ and node $$$j$$$ in the tree.

Given $$$n$$$, output the number of different$$$^\ddagger$$$ Manhattan trees with nodes numbered from $$$1$$$ to $$$n$$$, modulo $$$998244353$$$.

$$$^*$$$ The Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ in a two-dimensional plane is defined as $$$|x_1 - x_2| + |y_1 - y_2|$$$.

$$$^\dagger$$$ The distance between two nodes $$$i$$$ and $$$j$$$ in a tree is defined as the number of edges in the simple path between node $$$i$$$ and node $$$j$$$.

$$$^\ddagger$$$ We call tree $$$T_1$$$ and tree $$$T_2$$$ different if and only if there's an edge $$$(u, v)$$$ such that $$$(u, v) \in T_1$$$ and $$$(u, v) \notin T_2$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases.

For each test case:

  • The only line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^6$$$).
Output

For each test case, output in a new line — the number of different Manhattan trees, modulo $$$998244353$$$.

Example
Input
6
2
3
6
7
996
999999
Output
1
3
1290
16170
412965036
886558470
Note

In the third test case ($$$n=6$$$), for example, the following tree is a Manhattan tree

because there exist $$$6$$$ points $$$(x_1, y_1), (x_2, y_2), \ldots, (x_6, y_6)$$$ in a two-dimensional plane such that for any $$$i, j$$$ ($$$1 \leq i \lt j \leq 6$$$), the Manhattan distance from $$$(x_i, y_i)$$$ to $$$(x_j, y_j)$$$ is equal to the distance between node $$$i$$$ and node $$$j$$$ in the tree.

An example of the possible 6 points.

However, the following tree is not a Manhattan tree.

F. Cool Operations
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n$$$ and $$$q$$$ and two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$.

You need to answer $$$q$$$ queries. In the $$$i$$$-th query, you're given three integers $$$k_i, l_i$$$, and $$$r_i$$$.

At first, a variable $$$x$$$ is set to $$$k_i$$$. Then, for each $$$j$$$ from $$$l_i$$$ to $$$r_i$$$, you must choose exactly one of the following two types of operations:

  1. set $$$x := x + a_j$$$;
  2. set $$$x := \max(x, b_j)$$$.

You need to find the maximum possible value of $$$x$$$ for each query.

Input

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases.

  • The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n,q \leq 5 \cdot 10^5$$$);
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$);
  • The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).

Each of the next $$$q$$$ lines contains three integers $$$k_i, l_i$$$, and $$$r_i$$$ ($$$-10^9 \leq k_i \leq 10^9, 1 \le l_i \le r_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$5 \cdot 10^5$$$.

Output

For each query, output an integer in a new line  — the maximum possible value of $$$x$$$.

Examples
Input
1
4 5
10 2 3 -1
20 24 28 -10
8 1 2
17 1 2
19 2 3
25 2 3
-2 4 4
Output
24
29
28
30
-2
Input
1
5 5
756829654 557600139 843962687 -24632597 -866775049
505319834 616877613 657487273 912786344 924284486
481299777 1 3
-566119234 2 4
478992801 1 2
-694494781 3 5
-579759578 1 4
Output
2639692257
1460840300
1793422594
924284486
1906882660
Note

In the first query of the first test case, we have $$$x=8$$$ at first. We can do the following operations:

  1. for $$$j=1$$$, set $$$x := x+a_1 =8+10=18$$$;
  2. for $$$j=2$$$, set $$$x := \max(x, b_2)=\max(18,24)=24$$$.

It can be proven that $$$24$$$ is the maximum possible value of $$$x$$$.

In the second query of the first test case, we have $$$x=17$$$ at first. We can do the following operations:

  1. for $$$j=1$$$, set $$$x := x+a_1 =17+10=27$$$;
  2. for $$$j=2$$$, set $$$x := x+a_2 =27+2=29$$$.

It can be proven that $$$29$$$ is the maximum possible value of $$$x$$$.

G. Yet Yet Another Binary String Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can do the following operation any number of times:

  • Choose an index $$$i$$$ ($$$1 \lt i \lt n$$$), which satisfies $$$a_{i-1} \neq a_{i+1}$$$, then flip $$$a_i$$$. That is, change $$$a_i$$$ to $$$1$$$ if $$$a_i=0$$$, and change $$$a_i$$$ to $$$0$$$ otherwise ($$$a_i=1$$$).

Find the minimum number of operations to change $$$a$$$ to $$$b$$$. If you cannot change $$$a$$$ to $$$b$$$, output $$$-1$$$ instead.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 4 \cdot 10^5$$$), the length of the binary strings $$$a$$$ and $$$b$$$.
  • The second line contains a binary string $$$a$$$ of length $$$n$$$.
  • The third line contains a binary string $$$b$$$ of length $$$n$$$.

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

Output

For each test case, output a single line containing the minimum number of operations to change $$$a$$$ to $$$b$$$. If you can not change $$$a$$$ to $$$b$$$, output $$$-1$$$ instead.

Example
Input
5
3
000
011
3
000
111
3
000
000
4
0010
0100
5
11101
10011
Output
-1
-1
0
2
3
Note

In the first and second test cases, you cannot change $$$a$$$ to $$$b$$$.

In the third test case, $$$a$$$ and $$$b$$$ are already equal, so you don't need to do any operations.

In the fourth test case, you can change $$$a$$$ to $$$b$$$ after the following two operations:

  1. Choose $$$i=2$$$, which satisfies $$$a_{i-1} \neq a_{i+1}$$$, then flip $$$a_2$$$. After that, $$$a=0110$$$;
  2. Choose $$$i=3$$$, which satisfies $$$a_{i-1} \neq a_{i+1}$$$, then flip $$$a_3$$$. After that, $$$a=0100=b$$$.

It can be proven that $$$2$$$ is the minimum number of operations.

H. Xor and Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

Construct a permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ of the integers $$$\{0,1,\ldots,n-1\}$$$, such that $$$$$$f(p)=\sum_{i=0}^{n-2} (p_i \oplus p_{i+1})$$$$$$ is minimum possible.

Here, $$$\oplus$$$ denotes the bitwise XOR operation (https://en.wikipedia.org/wiki/Bitwise_operation#XOR)

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 500)$$$, representing the number of test cases.

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$, which denotes the size of the permutation.

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

Output

For each test case, output a single line containing the permutation $$$p$$$ of $$$\{0, 1, \dots, n-1\}$$$ such that $$$f(p)=\sum_{i=0}^{n-2} (p_i \oplus p_{i+1})$$$ is minimum possible.

Example
Input
2
2
4
Output
1 0
3 2 0 1
Note

In the first test case, $$$f(p)=0 \oplus 1=1$$$, which is the minimum possible. Another valid permutation is $$$p=[0,1]$$$.

In the second test case, $$$f(p)=(3 \oplus 2)+(2 \oplus 0)+(0 \oplus 1)=1+2+1=4$$$, which is the minimum possible. Other valid permutations, such as $$$p=[0,1,3,2]$$$, also exist.

I. Mega Polynomial
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two polynomials $$$f(x) = Ax + B$$$ and $$$g(x) = Cx^n + Dx^{n-1}$$$. Your task is to find the minimum integer $$$k$$$, such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$.

Here, $$$g^{(k)}(x)$$$ represents taking the derivative of $$$g(x)$$$ exactly $$$k$$$ times.

Formally,

  • $$$g^{(0)}(x) = g(x)$$$,
  • $$$g^{(k)}(x) = \frac{d}{dx} \left( g^{(k-1)}(x) \right)$$$ for $$$k \geq 1$$$,

and

  • $$$\frac{d}{dx} \left( Ex^m + Fx^{m-1} \right) = mEx^{m-1} + (m-1)Fx^{m-2}$$$ for $$$m \gt 1$$$,
  • $$$\frac{d}{dx} \left( Gx \right) = G$$$,
  • $$$\frac{d}{dx} \left( G \right) = 0$$$,

where $$$E$$$, $$$F$$$, and $$$G$$$ are constants.

For example, for $$$g(x) = x^3 + 3x^2$$$, we can find that:

  • $$$g^{(1)}(x) = 3x^2 + 6x$$$,
  • $$$g^{(2)}(x) = 6x + 6$$$,
  • $$$g^{(3)}(x) = 6$$$,
  • $$$g^{(4)}(x) = 0$$$.

We say that a polynomial $$$P_1(x)$$$ is divisible by $$$P_2(x)$$$ if and only if there exists a polynomial $$$Q(x)$$$ such that $$$P_1(x) = Q(x)P_2(x)$$$, where the coefficients of $$$Q$$$ are integers.

Input

The first line contains one positive integer $$$t$$$ ($$$1\leq t \leq 10^5$$$) — the number of test cases.

Each test case consists of one line which contains $$$5$$$ integers $$$A,B,C,D,n$$$ ($$$1\leq A,B,C,D,n\leq 2\cdot 10^5$$$).

Output

For each test case, output the minimum integer $$$k$$$, such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$.

Example
Input
6
1 2 2 4 1
4 2 3 3 4
2 4 1 3 3
2 1 5 2 4
131296 123463 91609 133724 142208
172458 127836 190471 141192 190476
Output
0
2
4
5
50599
190477
Note

In the first test case, $$$f(x)=x+2$$$ and $$$g(x)=2x+4$$$. We can see that $$$g^{(0)}(x)$$$ is divisible by $$$f(x)$$$ because $$$g^{(0)}(x)=g(x)=2x+4=2 \cdot f(x)$$$. So, the answer is $$$0$$$.

In the second test case, $$$f(x)=4x+2$$$ and $$$g(x)=3x^4+3x^3$$$. We can see that $$$k=2$$$ is the minimum integer such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$ because $$$g^{(2)}(x)=36x^2+18x=9x \cdot f(x)$$$.

In the third test case, $$$f(x)=2x+4$$$ and $$$g(x)=x^3+3x^2$$$. We can see that $$$k=4$$$ is the minimum integer such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$ because $$$g^{(4)}(x)=0=0 \cdot f(x)$$$.

Note that although $$$g^{(1)}(x)=3x^2+6x=\frac{2}{3}x \cdot f(x)$$$, $$$g^{(1)}(x)$$$ is not divisible by $$$f(x)$$$ since $$$\frac{2}{3}$$$ is not an integer.

J. Equal Node Sum
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You're given a rooted tree with $$$n$$$ vertices. The root node is $$$1$$$. You can set the weight of each edge to either $$$0$$$ or $$$1$$$. We call the sum value of node $$$i$$$ the sum of the weights of all edges incident to it.

Count the number of different assignments of edge weights that satisfy the following condition.

  • For each non-leaf node$$$^\dagger$$$, its sum value is equal to the sum value of every other non-leaf node.

Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A node is called a non-leaf node if and only if it is the root node $$$1$$$ or there are at least $$$2$$$ edges incident to it.

Input

The input consists of multiple test cases. The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$), the number of nodes in the tree.
  • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), indicating an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given input forms a tree.

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

Output

For each test case, output a single integer representing the number of different trees satisfying the given condition, modulo $$$998\,244\,353$$$.

Example
Input
5
3
1 2
1 3
3
1 2
2 3
4
1 4
2 4
3 1
6
1 4
2 3
3 6
4 3
5 2
8
1 2
2 4
3 4
4 8
5 1
6 4
7 3
Output
4
2
4
3
6
Note

In the first test case, there is only one non-leaf node: node $$$1$$$. You can set edge weights arbitrarily; thus, there are $$$4$$$ different assignments of edge weights.

In the second test case, there are two non-leaf nodes: nodes $$$1$$$ and $$$2$$$. There are $$$2$$$ valid assignments as shown below.

The two valid assignments.

K. Mad MAD Sum III
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two even integers $$$n$$$ and $$$m$$$.

We define the $$$\operatorname{MAD}$$$ (Maximum Appearing Duplicate) of an array as the largest number that appears at least twice in the array. If there is no number that appears at least twice, the $$$\operatorname{MAD}$$$ value is $$$0$$$.

For example, $$$\operatorname{MAD}([1, 2, 1]) = 1$$$, $$$\operatorname{MAD}([2, 2, 3, 3]) = 3$$$, $$$\operatorname{MAD}([1, 2, 3, 4]) = 0$$$.

Construct an array $$$a$$$ of length $$$n$$$ satisfying:

  • $$$0 \leq a_i \leq n$$$ for all $$$1 \le i \le n$$$;
  • $$$\displaystyle \sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=m. $$$

If no such array exists, output $$$-1$$$ instead.

Input

The first line contains one positive integer $$$t\;(1\leq t \leq 10^3)$$$ — the number of test cases.

Each test case consists of one line which contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \le 10^4$$$, $$$0 \le m \le \frac{n \cdot n \cdot (n-1)}{2}$$$). It is guaranteed that $$$n$$$ and $$$m$$$ are both even.

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

Output

For each test case, output an array $$$a$$$ of length $$$n$$$ that satisfies the given conditions. If no such array exists, output $$$-1$$$ instead.

Example
Input
4
2 0
4 10
4 22
8 40
Output
0 0
4 2 2 4
-1
5 2 1 2 1 5 2 1
Note

In the first test case, $$$$$$\sum_{1 \le l \lt r \le n} \operatorname{MAD}([a_l,a_{l+1}, \ldots, a_r])=\operatorname{MAD}([a_1,a_2])=\operatorname{MAD}([0,0])=0. $$$$$$

In the second test case, the following table summarizes the $$$\operatorname{MAD}$$$ of each subarray. $$$$$$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline 1 & & 0 & 2 & 4 \\ 2 & & & 2 & 2 \\ 3 & & & & 0 \\ 4 & & & & \end{array} $$$$$$ The sum of all $$$\operatorname{MAD}$$$ values is $$$10$$$, as required.

In the third test case, it is impossible to construct such an array.

L. Enigmatic Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game on an array $$$a$$$ of length $$$n$$$. They take turns performing the operation. Alice takes the lead. The person who cannot make a move loses.

In an operation, a player can:

  • choose a range $$$[l,r]$$$ ($$$1 \leq l \leq r \leq 10^9$$$);
  • if $$$l \lt r$$$, choose all indices $$$i$$$ such that $$$a_i \in [l,r-1]$$$ and decrease $$$a_i$$$ by $$$1$$$;
  • then, choose some (possibly zero) indices $$$i$$$ such that $$$a_i=r$$$ and decrease $$$a_i$$$ by $$$1$$$.
Afterwards, at least one value of $$$a_i$$$ must have decreased by $$$1$$$. Determine if Alice has a winning strategy.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output

For each test case, if Alice has a winning strategy, output YES. Otherwise, output NO.

Example
Input
6
7
1 3 1 3 3 4 5
4
1 1 1 1
1
1000000000
3
1 2 3
4
1 2 3 4
8
6 10 9 2 8 6 5 4
Output
YES
YES
NO
NO
YES
NO
Note

In the first test case, Alice can choose the range $$$[1,3]$$$, then choose all indices satisfying $$$a_i \in [1,2]$$$ and decrease $$$a_i$$$ by $$$1$$$. In other words, $$$a_1$$$ and $$$a_3$$$ are decreased by $$$1$$$. After that, $$$a=[0,3,0,3,3,4,5]$$$. Then, Alice can choose some $$$i$$$ satisfying $$$a_i=3$$$. In this case, Alice chooses $$$i=2,4$$$. After that,$$$a=[0,2,0,2,3,4,5]$$$;

It can be proven Alice has a winning strategy after the operation above.

In the second test case, Alice can choose $$$[1,1]$$$. Then, Alice can choose some indices $$$i$$$ satisfying $$$a_i=1$$$. Here, Alice chooses $$$i=1,2,3,4$$$. After this operation, $$$a=[0,0,0,0]$$$ and Alice wins.

M. Closed Paths
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes and a fixed even integer $$$k$$$. Node $$$i$$$ has weight $$$a_i$$$.

A closed path on a tree is a path that starts and ends at the same node. A closed path may visit the same node multiple times. A closed path of length $$$k$$$ that starts at node $$$1$$$ can be written as $$$x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{k+1}$$$, where:

  • $$$x_1 = x_{k+1} = 1$$$;
  • node $$$x_i$$$ and $$$x_{i+1}$$$ are adjacent on the tree.

The score of the closed path $$$x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{k+1}$$$ is defined as $$$\sum_{i=1}^{k+1} a_{x_i}$$$.

You need to answer $$$q$$$ queries. In the $$$i$$$-th query, you are given two numbers $$$p_i$$$ and $$$v_i$$$, which means you should update the value of $$$a_{p_i}$$$ to $$$v_i$$$. After the update, you need to find the score of a closed path of length $$$k$$$ starting at node $$$1$$$ that has the maximum possible score. Note that the updates are permanent.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2.5 \cdot 10^4$$$), the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$2 \leq k \leq 10^9$$$), the number of nodes in the tree and the length of the closed path, respectively. It is guaranteed that $$$k$$$ is even.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), the initial weights of the nodes.
  • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), representing an edge between nodes $$$u$$$ and $$$v$$$ in the tree. It is guaranteed that the given input forms a tree.
  • The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$), the number of queries.
  • The next $$$q$$$ lines each contain two integers $$$p_i$$$ and $$$v_i$$$ ($$$1 \leq p_i \leq n$$$, $$$1 \leq v_i \leq 10^9$$$), indicating that the value of $$$a_{p_i}$$$ should be updated to $$$v_i$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ respectively.

Output

For each query, output a single integer in a new line  — the maximum score of a closed path of length $$$k$$$ starting at node $$$1$$$ after applying the update.

Example
Input
2
4 6
1 4 3 1
1 2
1 3
4 3
2
2 3
4 2
2 1000000000
1 1
1 2
4
1 1000000000
2 1000000000
1 1
2 1
Output
13
15
500000001500000000
1000000001000000000
500000000500000001
1000000001
Note

In the first query of the first test case, $$$a=[1,3,3,1]$$$ and $$$k=6$$$. One of the possible closed paths of length $$$k$$$ that starts at node $$$1$$$ is $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 1$$$. The score of this closed path is $$$13$$$.

It can be proven that $$$13$$$ is the maximum possible score of a closed path.

In the first query of the first test case, $$$a=[1,3,3,2]$$$ and $$$k=6$$$. One of the possible closed paths of length $$$k$$$ that starts at node $$$1$$$ is $$$1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 1$$$. The score of this closed path is $$$15$$$.

It can be proven that $$$15$$$ is the maximum possible score of a closed path.