TheForces Round #33(Wow-Forces)
A. Mr. Wow and Lucky Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An array $$$c$$$ of size $$$n$$$ is called Lucky array if it satisfies the following conditions for every $$$i(1 \le i \le n)$$$:

  1. $$$c_i$$$ is either $$$0$$$ or $$$1$$$;
  2. $$$c_1 + c_2 + \ldots + c_i \le ⌊\frac{i}{2}⌋ $$$.

Mr. Wow has constructed a Lucky array $$$a$$$ of size $$$n$$$. Now he wants you to construct a Lucky array $$$b$$$ of size $$$n$$$ such that :

  1. $$$b ≠ a$$$. In other words, there is at least one index $$$i(1 \le i \le n)$$$ satisfying $$$a_i \neq b_i$$$;
  2. The value of $$$(b_1 + b_2 + \ldots + b_{n-1} + b_{n})$$$ is maximum possible.

If there is no Lucky array satisfying Mr. Wow's conditions, print $$$-1$$$ instead.

Note that, $$$⌊y⌋$$$ means the largest integer which is not greater than $$$y$$$, i.e., $$$⌊2.75⌋ = 2, ⌊3.99⌋ = 3, ⌊4⌋ = 4$$$.

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 a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the Lucky array $$$a$$$.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$0 \le a_{i} \le 1$$$).

It is guaranteed that the given array $$$a$$$ is a Lucky array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print $$$-1$$$ if there is no Lucky array satisfying Mr. Wow's conditions.

Otherwise, print $$$n$$$ space-separated integers $$$b_i$$$ ($$$0 \le b_{i} \le 1$$$) which satisfy the conditions by Mr. Wow.

Example
Input
5
1
0
2
0 1
4
0 0 1 0
5
0 1 0 0 1
6
0 0 0 0 0 0
Output
-1
0 0
0 1 0 1
0 0 1 1 0
0 0 1 1 0 1

B. Mr. Wow and Dislikes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Wow doesn't like arrays which contain positive integers. He is allowed to do the following operation on a given array $$$c$$$ of length $$$n$$$ by using two positive integers $$$a$$$ and $$$b$$$ $$$(a \gt b)$$$ :

  1. Choose any $$$i(1 \le i \le n)$$$;
  2. Set $$$c_i := c_i-a$$$, and $$$c_j =: c_j-b$$$ for every $$$j(1 \le j \le n, j ≠ i)$$$.

Help Mr. Wow with the minimum number of operations required to change the array $$$c$$$, such that it doesn't contain positive integers.

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 three space separated integers $$$n, a, b$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le b \lt a \le 10^9$$$) — the length of the array $$$c$$$ and variables required to do operations.

The second line of each test case contains $$$n$$$ space separated integers $$$c_{i}$$$ ($$$-10^9 \le c_{i} \le 10^9$$$).

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

Output

For each test case, print a single integer — minimum number of operations required to change the array $$$c$$$, such that it doesn't contain positive integers.

Example
Input
5
3 2 1
1 2 2
4 3 1
4 -7 9 -10
5 8 3
3 6 9 6 10
6 11 6
100 43 34 4 56 89
6 12 6
-1 -2 -3 -4 0 -11
Output
2
4
2
12
0
Note

In the $$$3$$$-rd test case, Mr. Wow can do the following two operations:

  1. Choose $$$i=3$$$. After that, $$$c=[0, 3, 1, 3, 7]$$$;
  2. Choose $$$i=5$$$. After that, $$$c=[-3, 0, -2, 0, -1]$$$.

It can be proven $$$2$$$ reaches the minimum.

C. Mr. Wow and Spells
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Wow is playing a computer game. There are $$$n$$$ monsters arranged from left to right and numbered $$$1, 2, ...., n$$$. The $$$i$$$-th monster from the left has $$$h_{i}$$$ health points. A monster will be dead if it's health points become less than or equal to $$$0$$$.

To kill the monsters, Mr. Wow can use the spells. A single spell means :

  1. Choose any arbitrary integer $$$x (1 \le x \le 10^9)$$$, which is the energy of the current spell (note that the energy of the spell might be different in different spells).
  2. Do the following for every $$$i(1 \le i \le n)$$$ from left to right :
    • If $$$x \le h_{i}$$$, then decrease $$$h_i$$$ by $$$x$$$ and make $$$x = 0$$$.
  3. If the current spell isn't used on any monster, or at least one monster died, the game will end.

What is the maximum number of spells Mr. Wow can use before the game ends?

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 a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of monsters.

The second line of each test case contains $$$n$$$ space-separated integers $$$h_{i}$$$ ($$$1 \le h_{i} \le 10^9$$$).

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

Output

For each test case, print a single integer — the maximum number of spells Mr. Wow can use before the game ends.

Example
Input
5
3
1 2 3
3
3 2 1
3
2 1 4
4
2 3 8 4
4
7 17 8 11
Output
1
3
3
7
23
Note

In the $$$1$$$-st test case, for any value of $$$x$$$, the game will end after using $$$1$$$ spell.

In the $$$3$$$-rd test case, we can do the following $$$3$$$ operations:

  1. Choose $$$x=1$$$. After that, $$$h=[1,1,4]$$$;
  2. Choose $$$x=3$$$; After that, $$$h=[1,1,1]$$$;
  3. Choose $$$x=1$$$; After that, $$$h=[0,1,1]$$$. The game ends because the first monster is dead.

It can be proven $$$3$$$ reaches the maximum.

D. Mr.Wow and Multiset
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Wow has a multiset $$$S$$$ of size $$$n$$$. At first, $$$S = \{1,2,\ldots,n\}$$$.

Mr. Wow can do the following operation exactly $$$(n-1)$$$ times:

  • Choose two elements $$$x, y$$$ in $$$S$$$(the value of $$$x$$$ and $$$y$$$ may be equal), remove them from $$$S$$$, then insert $$$(x-y)$$$ in $$$S$$$.

Determine if it's possible to make $$$S = \{m\}$$$ after $$$(n-1)$$$ operations. If it is possible, output any scheme.

Input

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

For each test case, there is a single line containing two integers $$$n$$$ and $$$m$$$ $$$(2 \leq n \leq 2 \cdot 10^5,-\frac{n(n+1)}{2} \leq m \leq \frac{n(n+1)}{2})$$$.

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

Output

For each test case:

  • If it's possible to make $$$S = \{m\}$$$ after the $$$(n-1)$$$ operations, print "YES" on a new line. Otherwise, print "NO" on a new line.
  • If "YES" is printed, on the next $$$(n-1)$$$ lines, print two integers $$$x_i, y_i$$$ in each line, representing the pairs of elements chosen in the $$$i$$$-th operation. In other words, in the $$$i$$$-th operation, you choose two elements $$$x_i$$$ and $$$y_i$$$ which are already in $$$S$$$, remove them from $$$S$$$, then insert $$$(x_i-y_i)$$$ in $$$S$$$.
Example
Input
5
3 0
3 1
4 6
4 10
5 -11
Output
YES
3 2
1 1
NO
YES
2 3
-1 4
1 -5
NO
YES
2 3
-1 4
-5 5
-10 1
Note

For the $$$1$$$-st test case, $$$S=\{1,2,3\}$$$ initially.

You can make $$$S = \{0\}$$$ using the following scheme:

  • In the first operation, you choose $$$x_1=3$$$ and $$$y_1=2$$$ in $$$S$$$, remove them from $$$S$$$, then insert $$$(x_1-y_1)=3-2=1$$$ in $$$S$$$. Currently $$$S=\{1,1\}$$$;
  • In the second operation, you choose $$$x_2=1$$$ and $$$y_2=1$$$ in $$$S$$$, remove them from $$$S$$$, then insert $$$(x_2-y_2)=1-1=0$$$ in $$$S$$$. Currently $$$S=\{0\}$$$.

For the $$$2$$$-nd test case, you can not make $$$S = \{1\}$$$.

E. Mr.Wow and Hidden Permutation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Mr. Cow has a hidden permutation $$$p$$$ of length $$$n$$$. It is guaranteed that $$$\bf{n\ mod\ 4 = 2}$$$.

Mr. Wow doesn't know anything about this permutation. Mr. Cow asked him to find any permutation $$$q$$$ of length $$$n$$$, such that $$$f(p,q)=|p_{q_{1}} - p_{q_{2}}| + |p_{q_{2}} - p_{q_{3}}| + \ldots +|p_{q_{n-1}} - p_{q_{n}}| + |p_{q_{n}} - p_{q_{1}}| $$$ is maximum possible.

To find the permutation $$$q$$$, Mr. Wow is allowed to ask the following question to Mr.Cow:

  • $$$? \ i_1 \ i_2 \ .... \ i_{(\frac{n}{2}-1)} \ i_{(\frac{n}{2})} \ (1 \le i_j \le n, 1 \le j \le \frac{n}{2}, i_{j} ≠ i_{k}$$$ for $$$j ≠ k)$$$. In other words, he will give exactly $$$(\frac{n}{2})$$$ distinct indices to Mr. Cow. After that, Mr. Cow will give him the median of $$$p_{i_1} , p_{i_2} , \ldots , p_{i_{(\frac{n}{2}-1)}} , p_{i_{(\frac{n}{2})}}$$$.

Help Mr. Wow to find any permutation $$$q$$$ such that $$$f(p,q)$$$ reaches maximum by asking at most $$$n + 30$$$ questions.

Input

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

For each test case, the only line contains a single integer $$$n$$$ $$$(2 \le n \le 1002)$$$ — the length of the hidden permutation. It is guaranteed that $$$\bf{n\ mod\ 4 = 2}$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$1002$$$.

Interaction

For each test case, the interaction starts with reading $$$n$$$.

Then you are allowed to ask atmost $$$n+30$$$ queries of the following way

$$$? \ i_1 \ i_2 \ .... \ i_{(\frac{n}{2}-1)} \ i_{(\frac{n}{2})}$$$.

After each query, you should read an integer : the median of $$$p_{i_1} , p_{i_2} , \ldots , p_{i_{(\frac{n}{2}-1)}} , p_{i_{(\frac{n}{2})}}$$$.

When you guessed any permutation $$$q$$$, print a single line $$$! \ q_1 \ q_2 \ .... \ q_{n-1} \ q_{n}$$$.

Outputting the answer does not count as a query.

The interactor for this problem is not adaptive. The permutation $$$p$$$ is fixed before any queries are made.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2

6

3

5

6

2

4
Output

? 6 2 5

? 2 4 1

! 4 6 1 5 2 3

? 4 3 5

? 1 6 2

! 4 2 1 6 3 5
Note

The hidden permutation in the $$$1$$$-st test case is $$$p=[5,6,2,4,1,3]$$$.

For $$$q=[4,6,1,5,2,3]$$$, $$$f(p,q)=|p_4-p_6|+|p_6-p_1|+|p_1-p_5|+|p_5-p_2|+|p_2-p_3|+|p_3-p_4|=1+2+4+5+4+2=18$$$.

It can be proven $$$18$$$ is the maximum of $$$f(p,q)$$$.

The hidden permutation in the $$$2$$$-nd test case is $$$p=[3,4,1,2,5,6]$$$.

F. Mr.Wow and Decoding
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr.Wow has an $$$0$$$-indexed integer array $$$b=[b_0, b_1, .... , b_{n-2}, b_{n-1}]$$$ containing $$$n$$$ elements. It is guaranteed that $$$n$$$ is even.

An array $$$a$$$ of size $$$n$$$ is called valid only if:

  • For every $$$0 \le i \le n-1$$$,
    1. $$$0 \le a_i \le 10^{18}$$$.
    2. $$$b_{i} \le (a_{i} + a_{i+1} + \ldots + a_{(i+(\frac{n}{2})-2)\%n} + a_{(i+(\frac{n}{2})-1)\%n})$$$ holds.

Here $$$\%$$$ represents the modular operation.

Find the minimum value of $$$(a_0+a_1+\ldots+a_{n-1})$$$ among all valid array $$$a$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the length of the array $$$a$$$. It is guaranteed that $$$n$$$ is even.

The second line of each test case contains $$$n$$$ space separated integers $$$b_{i}$$$ ($$$0 \le b_{i} \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum value of $$$(a_0+a_1+\ldots+a_{n-1})$$$ among all valid array $$$a$$$.

Example
Input
4
6
1 2 3 4 5 6
6
7 3 5 12 15 10
8
7 0 8 8 0 0 0 10
10
0 0 100 0 0 67 0 4252 99 0
Output
9
19
18
4352
Note

In the $$$1$$$-st test case, one of the possible arrays is $$$a = [0,0,3,0,0,6]$$$.

In the $$$2$$$-nd test case, one of the possible arrays is $$$a = [6,1,0,2,3,7]$$$.