Codeforces Round 1120 (Div. 2)
A. Min Max Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie and Elsie are playing a game on a binary array $$$a$$$ of length $$$n$$$.

The players alternate turns, with Bessie moving first. On Bessie's turn, she chooses two adjacent elements $$$x$$$ and $$$y$$$ and replaces them with the single value $$$\max(x,y)$$$.

On Elsie's turn, she chooses two adjacent elements $$$x$$$ and $$$y$$$ and replaces them with the single value $$$\min(x,y)$$$.

After each move, the length of the array decreases by $$$1$$$. The game ends when only one element remains. Bessie wins if the final element is $$$1$$$, and Elsie wins if the final element is $$$0$$$.

Assuming both players play optimally, determine who wins.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$).

Output

For each test case, you should output the name of who wins on a new line.

Example
Input
3
5
1 0 1 0 1
3
0 0 1
4
1 1 0 0
Output
Bessie
Elsie
Bessie
Note

For the first test case, Bessie can guarantee a win. One possible game is as follows: $$$$$$ [\color{red}{1},\color{red}{0},1,0,1] \to [1,\color{red}{1},\color{red}{0},1] \to [\color{red}{1},\color{red}{0},1] \to [\color{red}{1},\color{red}{1}] \to [1]. $$$$$$ The final value is $$$1$$$, so Bessie wins (the red highlight denotes the two adjacent elements picked on that turn).

For the second test case, no matter which move Bessie makes, Elsie can make the final value $$$0$$$. Therefore, Elsie wins.

For the third test case, one possible winning game for Bessie is: $$$$$$ [1,\color{red}{1},\color{red}{0},0] \to [1,\color{red}{1},\color{red}{0}] \to [\color{red}{1},\color{red}{0}] \to [1]. $$$$$$ The final value is $$$1$$$, so Bessie wins.

B. Min Matrices
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer John heard from Elsie that Bessie's favorite number is $$$k$$$, so he wants to surprise her with a handcrafted present.

For a 2D matrix $$$B$$$, let $$$f(B)$$$ denote the set of the minimum element of each row and each column of $$$B$$$.

Farmer John wants you to show him an $$$n \times n$$$ matrix $$$A$$$ consisting of each number from $$$1$$$ to $$$n^2$$$ exactly once such that $$$|f(A)| = k$$$, or state that it is impossible.

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 $$$k$$$ ($$$1 \le n \le 1000, 0 \le k \le 2n$$$) — the size of the matrix and the goal value of $$$|f(A)|$$$.

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

Output

If there is no such matrix, print $$$-1$$$. Otherwise, print $$$n$$$ lines with $$$n$$$ integers each — an $$$n \times n$$$ matrix that satisfies the conditions of the problem.

If there are multiple solutions, you may output any of them.

Example
Input
5
3 0
3 5
5 5
4 3
1 1
Output
-1
8 5 9
6 3 7
2 1 4
16 14 17 15 3
25 22 5 23 24
8 1 9 6 7
4 18 21 19 20
12 10 13 2 11
-1
1 
Note

In the first test case, we can see that it is impossible to construct such a $$$3 \times 3$$$ matrix where $$$f(A)$$$ is empty.

In the second test case, we can see the minimums of the rows are $$$[5, 3, 1]$$$ respectively, and the minimums of the columns are $$$[2, 1, 4]$$$ respectively. Therefore, $$$f(A) = \{1, 2, 3, 4, 5\}$$$, so $$$|f(A)| = 5$$$ as desired.

C1. Floor of MEX (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The difference between the versions is that in this version, you only need to find one subset that satisfies the constraints. You can hack only if you solved all versions of this problem.

Let $$$$$$ f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right), $$$$$$ where $$$S$$$ is a set of non-negative integers and $$$x$$$ is a positive integer. $$$^{\text{∗}}$$$

Farmer John chooses a (possibly empty) subset $$$A\subseteq \{0,1,\ldots,n-1\}$$$. He then constructs an array $$$a$$$ of length $$$n$$$, where $$$a_k = f(A,k)$$$ for every $$$1\le k\le n$$$.

Bessie, being a mischievous cow, hides the set $$$A$$$. Farmer John is left only with the array $$$a_1,a_2,\ldots,a_n$$$.

Your task is to construct any (possibly empty) subset $$$B\subseteq \{0,1,\ldots,n-1\}$$$ such that $$$f(B,k)=a_k$$$ for every $$$1 \le k \le n$$$. Farmer John will only give you arrays where such a $$$B$$$ exists.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(c)$$$ denotes the minimum excluded (MEX)$$$^{\text{∗}}$$$ of the collection $$$c$$$. (in this case, the minimum non-negative integer not present in the set)

Input

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq n$$$).

You will only be given arrays where there exists $$$B \subseteq \{0,1,\ldots,n-1\}$$$ such that $$$f(B,k)=a_k$$$ for every $$$1 \le k \le n$$$.

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

Output

For each test case, output two lines.

On the first line, output an integer $$$m$$$ — the size of the set $$$B$$$.

On the second line, output $$$m$$$ distinct integers $$$b_1,b_2,\ldots,b_m$$$ — the elements of $$$B$$$. If $$$m=0$$$, the second line should be empty.

The elements of $$$B$$$ may be printed in any order.

If there are multiple solutions, you may output any of them.

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

For the first test case, one possible answer is $$$$$$ B=\{1,2,3,4,5\}. $$$$$$ Then $$$$$$ f(B,1)=\text{mex}(\{1,2,3,4,5\})=0, $$$$$$ $$$$$$ f(B,2)=\text{mex}(\{0,1,2\})=3, $$$$$$ and $$$$$$ f(B,3)=f(B,4)=f(B,5)=2. $$$$$$ Finally, $$$$$$ f(B,6)=\text{mex}(\{0\})=1. $$$$$$ Thus the array is $$$[0,3,2,2,2,1]$$$.

For the second test case, one possible answer is $$$$$$ B=\{0,1\}. $$$$$$ Then $$$f(B,1)=2$$$, and for every $$$2\le k\le 5$$$, we have $$$$$$ \left\{\left\lfloor y/k\right\rfloor : y\in B\right\}=\{0\}, $$$$$$ so $$$f(B,k)=1$$$. Therefore, the array is $$$[2,1,1,1,1]$$$.

C2. Floor of MEX (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, you need to count how many sets satisfy the constraints. You can hack only if you solved all versions of this problem.

Let $$$$$$ f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right), $$$$$$ where $$$S$$$ is a set of non-negative integers and $$$x$$$ is a positive integer. $$$^{\text{∗}}$$$

Farmer John chooses a (possibly empty) subset $$$A\subseteq \{0,1,\ldots,n-1\}$$$. He then constructs an array $$$a$$$ of length $$$n$$$, where $$$a_k = f(A,k)$$$ for every $$$1\le k\le n$$$.

Bessie, being a mischievous cow, hides the set $$$A$$$. Farmer John is left only with the array $$$a_1,a_2,\ldots,a_n$$$.

Your task is to count how many sets (including the empty set) $$$B \subseteq \{0,1,\ldots,n-1\}$$$ such that $$$f(B,k)=a_k$$$ for every $$$1 \le k \le n$$$. Since the number can be very large, output it modulo $$$10^9+7$$$. Farmer John will only give you arrays where such a $$$B$$$ exists.

$$$^{\text{∗}}$$$$$$\operatorname{mex}(c)$$$ denotes the minimum excluded (MEX)$$$^{\text{∗}}$$$ of the collection $$$c$$$. (in this case, the minimum non-negative integer not present in the set)

Input

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq n$$$).

You will only be given arrays where there exists $$$B \subseteq \{0,1,\ldots,n-1\}$$$ such that $$$f(B,k)=a_k$$$ for every $$$1 \le k \le n$$$.

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

Output

For each testcase, output one number, the number of sets $$$B$$$ that satisfy the constraints modulo $$$10^9 + 7$$$.

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

For the first testcase, the $$$6$$$ subsets are $$$$$$\{1, 2, 5\}, \{1, 3, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 4, 5\}.$$$$$$

For the second testcase, the only subset that satisfies $$$f(B,k) = a_k$$$ for every $$$1 \le k \le n$$$ is $$$\{0, 1\}$$$.

D. Culling Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie is making a show called Moojutsu Cowsen. For one episode, she invites $$$n$$$ sorcerers and lines them up from left to right. The initial skill level of the $$$i$$$-th sorcerer is $$$a_i$$$.

The sorcerers compete in a king-of-the-hill tournament. The leftmost remaining sorcerer starts as the champion, and his current skill is equal to his initial skill.

Then, the champion faces each remaining sorcerer to his right, one by one. Suppose the current champion has skill $$$s$$$, and the next sorcerer has skill $$$x$$$.

If $$$s \lt x$$$, the champion forfeits. The next sorcerer becomes the new champion with skill $$$x$$$.

Otherwise, the champion fights and wins (the champion still wins when $$$s = x$$$). In this case, the champion's current skill becomes $$$s+x$$$.

Bessie finds forfeits boring, so before running the tournament, she may remove some sorcerers from the lineup.

You are given a permutation $$$p_1,p_2,\ldots,p_n$$$ of the integers from $$$1$$$ to $$$n$$$. For each $$$0 \le i \le n-1$$$, Bessie removes sorcerers $$$p_1,p_2,\ldots,p_i$$$ from the lineup. If $$$i=0$$$, no sorcerers are removed. The relative order of all remaining sorcerers does not change.

For each such $$$i$$$, determine how many forfeits happen when Bessie runs the tournament using only the remaining sorcerers.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\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$$$).

The third line of each test case contains a permutation $$$p_1,p_2,\ldots,p_n$$$ of the integers from $$$1$$$ to $$$n$$$.

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 $$$n$$$ integers.

The $$$i$$$-th integer should be the number of forfeits after removing sorcerers $$$p_1,p_2,\ldots,p_{i-1}$$$.

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

For the first test case, the answers are $$$2,1,0,0$$$.

Before any removals, the array is $$$[1,2,4,3]$$$. The champion with skill $$$1$$$ forfeits against skill $$$2$$$, and then the champion with skill $$$2$$$ forfeits against skill $$$4$$$. The champion with skill $$$4$$$ defeats skill $$$3$$$, so there are $$$2$$$ forfeits.

After removing sorcerer $$$1$$$, the remaining array is $$$[2,4,3]$$$. The champion with skill $$$2$$$ forfeits against skill $$$4$$$, and then the champion with skill $$$4$$$ defeats skill $$$3$$$, so there is $$$1$$$ forfeit.

After removing sorcerers $$$1$$$ and $$$2$$$, the remaining array is $$$[4,3]$$$. The champion defeats the only remaining sorcerer, so there are $$$0$$$ forfeits. After removing sorcerers $$$1$$$, $$$2$$$, and $$$3$$$, only one sorcerer remains, so there are also $$$0$$$ forfeits.

For the second test case, the answers are $$$1,0,2,1,0$$$.

Before any removals, the array is $$$[3,1,7,2,6]$$$. The champion with skill $$$3$$$ defeats skill $$$1$$$ and gains one skill point, then forfeits against skill $$$7$$$. After that, the champion defeats skills $$$2$$$ and $$$6$$$, so there is $$$1$$$ forfeit.

After removing sorcerer $$$3$$$, whose skill is $$$7$$$, the remaining array is $$$[3,1,2,6]$$$. The champion defeats every remaining sorcerer, so there are $$$0$$$ forfeits.

After also removing sorcerer $$$1$$$, the remaining array is $$$[1,2,6]$$$ The champion with skill $$$1$$$ forfeits against skill $$$2$$$, and then the champion with skill $$$2$$$ forfeits against skill $$$6$$$, so there are $$$2$$$ forfeits.

After also removing sorcerer $$$5$$$, the remaining array is $$$[1,2]$$$. There is $$$1$$$ forfeit. Finally, after also removing sorcerer $$$2$$$, only one sorcerer remains, so there are $$$0$$$ forfeits.

E. Traveling the World
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ islands, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th island has value $$$a_i$$$. The values $$$a_1,a_2,\ldots,a_n$$$ are strictly increasing, and $$$a_1=0$$$.

Farmer John wants to rearrange the islands. After rearranging them, their values form an array $$$b_1,b_2,\ldots,b_n$$$, which is a rearrangement of $$$a$$$.

Bessie then travels between islands according to the following rule. Suppose she is currently on the island in position $$$i$$$ after the rearrangement. Then Bessie may travel from the island in position $$$i$$$ to the island in position $$$j$$$ if $$$$$$ b_i + b_j = \max(b_i,b_{i+1},\ldots,b_n). $$$$$$

A rearrangement $$$b$$$ is called good if there exists a sequence of distinct positions $$$p_1,p_2,\ldots,p_n$$$ such that Bessie can travel from $$$p_i$$$ to $$$p_{i+1}$$$ for every $$$1\le i \lt n$$$. In other words, Bessie can visit all positions (and therefore all islands) exactly once by following valid travels.

Count the number of good rearrangements of the islands. Since the number can be large, output it modulo $$$10^9+7$$$.

Input

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

The first line of each test case contains $$$n$$$ ($$$4 \le n \le 2 \cdot 10^5$$$).

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

It is guaranteed that $$$a_1=0$$$ and $$$a_1 \lt a_2 \lt \cdots \lt a_n$$$.

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 — the number of good rearrangements $$$b$$$ of $$$a$$$, modulo $$$10^9+7$$$.

Example
Input
3
6
0 1 2 3 4 5
5
0 3 4 5 6
4
0 1 3 4
Output
12
0
4
Note

For the first testcase, one $$$b$$$ that works is $$$[2,1,0,5,3,4]$$$.

Note that Bessie can travel from $$$1 \to 5$$$ since $$$2 + 3 = b_1 + b_5 = \max(b_1,b_2,\ldots,b_6) = 5$$$.

Similarly, Bessie can travel from $$$5 \to 2$$$, $$$2\to 6$$$, $$$6\to 3$$$, $$$3\to 4$$$.

Thus, starting from island $$$1$$$, Bessie can follow the path $$$1\to 5\to 2\to 6\to 3\to 4$$$ which visits every island. Therefore, this rearrangement is good.

For the second testcase, it can be shown that there are no good rearrangements. Therefore, the answer is $$$0$$$.

F. PLUSworld
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer John is building PLUSworld, a giant barn complex with $$$n$$$ barns numbered from $$$1$$$ to $$$n$$$. For each $$$1 \le i \le n$$$, there is currently a one-way walkway from barn $$$i$$$ to barn $$$a_i$$$.

Before opening PLUSworld, Farmer John wants to reconfigure the roads so that, for every $$$1 \le i \le n$$$, the road from barn $$$i$$$ points to barn $$$b_i$$$. The target roads have the special property that each road points to its own barn or to a higher-numbered barn $$$(i \le b_i)$$$.

To do this, he sends Bessie to one barn of his choice. Let $$$p$$$ be the barn where Bessie is currently located. Bessie may perform the following operations any number of times:

  • Operation $$$1$$$: Increase the destination of the road from the current barn by $$$1$$$. More formally, set $$$a_p := a_p + 1$$$. This operation may only be performed if $$$a_p \lt n$$$.
  • Operation $$$2$$$: Follow the road from the current barn. More formally, set $$$p := a_p$$$.

Operation $$$1$$$ changes the array $$$a$$$, but Bessie stays at the same barn. Operation $$$2$$$ changes Bessie's current barn, but does not change the array.

Your goal is to make the array $$$a$$$ equal to the array $$$b$$$.

Determine whether this is possible. If it is possible, output any valid starting barn and any sequence of operations that makes $$$a=b$$$.

It can be shown that if a solution exists, then there exists one using at most $$$2n^2$$$ operations.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$\color{red}{i\le b_i}\le n$$$).

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

Output

For each test case, if it is impossible to make $$$a$$$ equal to $$$b$$$, output a single integer $$$-1$$$.

Otherwise, output two lines.

On the first line, output two integers $$$o$$$ and $$$p$$$ — the number of operations you will perform and the initial index you choose ($$$0 \leq o \leq 2n^2$$$, $$$1 \leq p \leq n$$$).

On the second line, output $$$o$$$ integers $$$c_1,c_2,\ldots,c_o$$$ ($$$1\le c_i\le 2$$$), where $$$c_i$$$ is the type of the $$$i$$$-th operation.

If $$$c_i=1$$$, you perform operation $$$1$$$ and set $$$a_p:=a_p+1$$$. This operation may only be used if $$$a_p \lt n$$$ at that moment.

If $$$c_i=2$$$, you perform operation $$$2$$$ and set $$$p:=a_p$$$.

After performing all $$$o$$$ operations, the array $$$a$$$ must be equal to $$$b$$$.

If there are multiple valid answers, you may output any of them.

Example
Input
9
3
1 2 3
2 3 3
2
2 2
1 2
5
1 1 1 4 5
2 3 4 5 5
3
1 1 1
1 2 3
3
1 1 1
3 2 3
3
1 1 3
1 2 3
4
1 1 1 4
3 3 4 4
4
1 4 3 4
1 4 3 4
5
1 3 4 5 4
2 3 4 5 5
Output
5 1
1 2 1 2 2
-1
12 1
1 2 1 1 2 1 1 1 2 1 2 2
-1
-1
2 2
1 2
12 1
1 1 2 1 2 1 1 2 1 1 2 2
0 1
7 1
1 2 2 2 2 1 2
Note

For the first test case, Bessie starts at barn $$$1$$$. She increases $$$a_1$$$ from $$$1$$$ to $$$2$$$, follows the road to barn $$$2$$$, and increases $$$a_2$$$ from $$$2$$$ to $$$3$$$. The resulting array is $$$[2,3,3]$$$, which is equal to $$$b$$$.

For the second test case, $$$a_1=2 \gt b_1=1$$$. Since road destinations can only be increased, it is impossible to make $$$a_1$$$ equal to $$$b_1$$$, so the answer is $$$-1$$$.

For the third test case, Bessie starts at barn $$$1$$$. She changes $$$a_1$$$ from $$$1$$$ to $$$2$$$ and follows the road to barn $$$2$$$. She then changes $$$a_2$$$ from $$$1$$$ to $$$3$$$ and moves to barn $$$3$$$, changes $$$a_3$$$ from $$$1$$$ to $$$4$$$ and moves to barn $$$4$$$, and finally changes $$$a_4$$$ from $$$4$$$ to $$$5$$$. The resulting array is $$$[2,3,4,5,5]$$$, which is equal to $$$b$$$.