Rutgers University Programming Contest Spring 2026 - Open Division
A. Fold Distance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas has been learning origami lately and is experimenting with grid-based folding patterns. To get started, he has made creases in a rectangular piece of paper to split it up into an $$$m \times n$$$ grid. Thomas has marked two of the grid cells and wants to know the minimum number of creases he has to fold along in order to get one of the marked cells to lie directly on top of the other.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers, $$$m$$$ and $$$n$$$ ($$$1 \le m, n \le 1000$$$) — the number of rows and columns of the grid, respectively.

The next line of each test case contains four integers, $$$r_1$$$, $$$c_1$$$, $$$r_2$$$, and $$$c_2$$$ ($$$1 \le r_1, r_2 \le m$$$ and $$$1 \le c_1, c_2 \le n$$$) — the coordinates of the first and second marked cells, respectively, where $$$(1, 1)$$$ is the top left cell and $$$(n, m)$$$ is the bottom right cell. It is guaranteed that the two marked cells are different.

Output

For each test case, output a single integer — the minimum number of crease folds required to land one of the marked cells on top of the other.

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

The first test case corresponds to the image above. Note that Thomas can only fold along the existing crease lines.

In the second test case, it can be proven that Thomas must make at least 3 folds.

B. The String Only Contains a, b, and c
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting only of the letters a, b, and c. You want to split $$$s$$$ into contiguous substrings such that the average number of distinct characters over all the substrings is exactly $$$2$$$. For example, here is one way you could split up the string abcabaaaaccbabcc (along with the number of distinct characters in each section):

Since the average number of characters in each substring is $$$\frac{3 + 1 + 3 + 1}{4} = 2$$$, this is a suitable way to split up the string.

Input

Each test consists of multiple test cases.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$s$$$. The next line of each test case contains a single string of length $$$n$$$ consisting only of the letters a, b, and c — the string $$$s$$$.

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

Output

For each test case, print YES if there is a valid way to split up the string $$$s$$$, and NO otherwise. You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).

Example
Input
4
16
abcabaaaaccbabcc
6
abcabc
5
aaaaa
2
cb
Output
YES
YES
NO
YES
Note

The first test case corresponds to the image above.

In the second test case, the string $$$s=$$$abcabc can be divided up into ab, ca, and bc, each of which contains two distinct characters.

In the third test case, we can prove that there is no suitable partition of $$$s$$$.

In the fourth test case, we can include all of $$$s$$$ in one substring, since there are two distinct characters in cb.

C. Cakenap Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a$$$ of length $$$n$$$.

You can perform the following three-step operation on $$$a$$$.

  1. Choose the length $$$k$$$ of a prefix of $$$a$$$ ($$$1\le k \le n$$$).
  2. Reverse the chosen prefix of $$$a$$$.
  3. Move the chosen prefix of $$$a$$$ to the back of $$$a$$$.

For example, here is one possible operation on a permutation of length 10:

Note that if $$$n$$$ is chosen as the length of the prefix, the operation reverses the permutation.

Find a construction using at most $$$2n$$$ operations to sort the permutation $$$a$$$ in ascending order.

It can be shown that this is always possible.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n \le 5000$$$) — the length of $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation $$$a$$$.

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

Output

The first line of output for each test case should contain a single integer $$$q$$$ ($$$0 \le q \le 2n$$$) — the number of operations you will perform.

The second line of output for each test case should contain $$$q$$$ integers — the length of the prefix for each operation you will perform, in order. After these operations, the permutation should be sorted.

If there are multiple solutions, you may print any.

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

In the first test case, $$$a$$$ is transformed into $$$[3, 1, 2]$$$ after the first operation, and into $$$[1, 2, 3]$$$ after the second.

In the second test case, $$$a$$$ is transformed into $$$[1, 2]$$$ after the first and only operation.

In the third test case, $$$a$$$ is transformed into $$$[1, 4, 3, 2]$$$ after the first operation, into $$$[2, 3, 4, 1]$$$ after the second, into $$$[4, 3, 2, 1]$$$ after the third, and into $$$[1, 2, 3, 4]$$$ after the fourth.

D. Doubting Thomas
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ valuable artifacts arranged in a row, where the $$$i$$$-th artifact has a cost $$$c_i$$$. Thomas is planning on stealing some of the artifacts. He is going to iterate through each artifact in order, and steal any artifact whose cost is at least the $$$\operatorname{MEX}$$$ of the artifacts he has already stolen.

The $$$\operatorname{MEX}$$$ of a set of integers is defined as the smallest non-negative integer which does not occur in the set. For example, the $$$\operatorname{MEX}$$$ of $$$\{0, 1, 2, 4\}$$$ is $$$3$$$, and the $$$\operatorname{MEX}$$$ of $$$\{1, 4, 6, 8\}$$$ is $$$0$$$.

For example, if Thomas has previously stolen artifacts with costs of $$$\{1, 2, 1, 0, 6, 5\}$$$, the next artifact he steals must have a cost of at least $$$3$$$.

There is a special artifact initially at position $$$k$$$ in the row, and your goal is to prevent Thomas from stealing it. To do so, you may swap the positions of any pair of artifacts. Is it possible to stop Thomas from stealing the special artifact, and if so, which swap should you make?

Input

Each test consists of multiple test cases.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le n$$$) — the number of artifacts and the initial position of the special artifact, respectively.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \cdots c_n$$$ ($$$0 \le c_i \le n$$$) — the costs of the artifacts, in order.

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

Output

For each test case, if it is impossible to stop Thomas from stealing the special artifact, print -1 -1.

Otherwise, print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$) — the positions of the two artifacts to swap. You are allowed to choose a pair with $$$i = j$$$, in which case no swap will be made.

If there are multiple solutions, you may print any.

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

In the first test case, we swap artifacts $$$3$$$ and $$$5$$$, so this is what the row of artifacts will look like before and after the swap (with the special artifact in red):

$$$$$$[1, 0, 1, \color{red}{2}, 2] \rightarrow [1, 0, 2, \color{red}{2}, 1]$$$$$$

After the swap, Thomas will make the following moves, where $$$S$$$ is the set of costs of artifacts Thomas has stolen.

  • For the first artifact, $$$S = \{\}$$$, with a $$$\operatorname{MEX}$$$ of $$$0$$$. Since $$$c_1 = 1 \ge 0$$$, he steals the first artifact and adds $$$1$$$ to $$$S$$$.
  • For the second artifact, $$$S = \{1\}$$$, with a $$$\operatorname{MEX}$$$ of $$$0$$$. Since $$$c_2 = 0 \ge 0$$$, he steals the second artifact and adds $$$0$$$ to $$$S$$$.
  • For the third artifact, $$$S = \{0, 1\}$$$, with a $$$\operatorname{MEX}$$$ of $$$2$$$. Since $$$c_3 = 2 \ge 2$$$, he steals the third artifact and adds $$$2$$$ to $$$S$$$.
  • For the fourth artifact, $$$S = \{0, 1, 2\}$$$, with a $$$\operatorname{MEX}$$$ of $$$3$$$. Since $$$c_4 = 2 \lt 3$$$, he does not steal the fourth artifact.
  • For the fifth artifact, $$$S = \{0, 1, 2\}$$$, with a $$$\operatorname{MEX}$$$ of $$$3$$$. Since $$$c_5 = 1 \lt 3$$$, he does not steal the fifth artifact.

Since he doesn't steal the special artifact on position $$$4$$$, we have succeeded.

In the second test case, we swap artifacts $$$1$$$ and $$$4$$$, so the artifacts will look like this before and after the swap:

$$$$$$[\color{red}{1}, 0, 1, 2, 2] \rightarrow [2, 0, 1, \color{red}{1}, 2]$$$$$$

Note that the position of the special artifact has changed, so our goal is to stop Thomas from stealing the artifact in position $$$4$$$ after the swap. If we simulate the process as in the first test case, we can see that Thomas will not steal it.

In the third test case, we can show that no matter what swap we make, Thomas will always steal the artifact with cost $$$0$$$.

In the fourth test case, since there are no artifacts with cost $$$0$$$, the $$$\operatorname{MEX}$$$ of the costs of the stolen artifacts will always be $$$0$$$, and Thomas will steal every artifact, no matter what swap is made.

E. BABA IS LOCKED
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a grid with $$$n$$$ rows and $$$m$$$ columns. In one move, you can move up, left, or right (not down), as long as you stay within the grid and never visit any square more than once.

How many ways are there to get from the bottom-left square to the top-right square?

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

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

Each test case consists of a single line containing two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 100$$$) — the number of rows and columns in the grid, respectively.

Note that there is no limit on the sum of $$$n$$$ or $$$m$$$ over all test cases.

Output

For each test case, print a single integer — the number of ways to get from the bottom-left square to the top-right square, modulo $$$998 \, 244 \, 353$$$.

Example
Input
2
2 3
3 4
Output
3
16
Note

In the first test case, there are $$$3$$$ possible paths:

F. Approximate Three Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$ and an integer $$$m$$$. Find three distinct indices $$$1 \le i, j, k \le n$$$ such that $$$m \le a_i + a_j + a_k \le 2m$$$, or report that no such indices exist.

Input

Each test consists of multiple test cases.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^8$$$) — the length of the array $$$a$$$ and the target sum, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^8$$$) — the array $$$a$$$ as described above.

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

Output

For each test case, if there is no solution, print a single integer $$$-1$$$.

Otherwise, print three distinct integers $$$i$$$, $$$j$$$, $$$k$$$ ($$$1 \le i, j, k \le n$$$) such that $$$m \le a_i + a_j + a_k \le 2m$$$.

If there are multiple solutions, you may print any.

Example
Input
4
5 10
1 4 6 9 2
5 20
1 4 6 9 2
3 1
3 4 5
10 22
5 1 2 9 3 1 1 3 10 6
Output
2 3 4
-1
-1
8 9 4
Note

In the first test case, we have $$$a_2 + a_3 + a_4 = 19$$$, which is in the range $$$[10, 20]$$$.

In the second test case, it can be shown that no triple satisfies the condition $$$20 \le a_i + a_j + a_k \le 40$$$.

G. Longest Step-function Subsequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We say that a sequence $$$x_1, x_2, \dots, x_n$$$ is a step-function if there exist two distinct numbers $$$A$$$ and $$$B$$$ and some index $$$1 \lt k \le n$$$ such that $$$x_i = A$$$ for $$$i \lt k$$$ and $$$x_i = B$$$ for $$$i \ge k$$$.

Informally, a step-function is a sequence that changes value exactly once, so that it looks like $$$[A, A, \dots, A, B, B, \dots, B]$$$.

For example, the sequences $$$[1, 1, 1, 3, 3, 3]$$$, $$$[7, 7, 7, 6]$$$, and $$$[100, 101, 101]$$$ are all step-functions, and the sequences $$$[1, 2, 3]$$$ and $$$[0, 0, 0, 0]$$$ are not.

You are given an array $$$a$$$ of length $$$n$$$. Your task is to find the length of the longest subsequence of $$$a$$$ that is a step-function. If there is no such subsequence, output $$$0$$$.

A sequence $$$x$$$ is a subsequence of another sequence $$$y$$$ if $$$x$$$ can be obtained by deleting several (possibly zero or all) elements from $$$y$$$, without changing the order of the remaining elements. For example, $$$[1, 3, 4, 7]$$$ is a subsequence of $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$, and $$$[3, 3]$$$ is a subsequence of itself, but $$$[4, 3]$$$ is not a subsequence of $$$[1, 2, 3, 4]$$$.

Input

Each test consists of multiple test cases.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  – the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the values in the array $$$a$$$.

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

Output

For each test case output a single integer  – the length of the longest subsequence of $$$a$$$ that is a step-function, or $$$0$$$ of no such subsequence exists.

Example
Input
4
11
2 1 3 1 2 1 0 2 0 3 0
8
6 6 6 7 7 6 6 6
4
0 0 0 0
14
-3 -1 -3 -1 -3 -1 -1 -2 -1 -2 -1 -1 -1 -4
Output
6
5
0
9
Note

In the first test case, the longest step-function subsequence is $$$[1, 1, 1, 0, 0, 0]$$$.

In the second test case, the longest step-function subsequences are $$$[6, 6, 6, 7, 7]$$$ and $$$[7, 7, 6, 6, 6]$$$. The subsequence $$$[6, 6, 6, 6, 6, 6]$$$ is longer, but it is not a step-function subsequence because it does not contain two distinct values.

In the third test case, there are no step-function subsequences because there is only one distinct value in the array.

H. NP-hard Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a run-twice (communication) problem.

Alice and Bob have the same undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Bob wants to construct a $$$3$$$-coloring$$$^{\text{∗}}$$$ of this graph.

Fortunately, Alice already has an array $$$c$$$ representing a $$$3$$$-coloring of this graph. However, the only way she can communicate with Bob is by sending him an array $$$a$$$ of length $$$k$$$ such that $$$0 \le k \le \lfloor \frac n 2 \rfloor$$$ and $$$a_i \in \{1, 2, 3\}$$$.

Bob wants to construct any $$$3$$$-coloring of the graph. Note that this $$$3$$$-coloring does not have to be the same as the array $$$c$$$.

Your task is to implement the strategy for both Alice and Bob.

$$$^{\text{∗}}$$$A 3-coloring is an array $$$x$$$ of size $$$n$$$ where $$$x_i \in \{1, 2, 3\}$$$ and $$$x_u \ne x_v$$$ for all edges $$$(u, v)$$$

Input

Your code will be run exactly two times on each test. On the first run, you will act as Alice, and on the second you will act as Bob.

First Run Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Alice.

Each test consists of multiple test cases.

The second line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 3 \cdot 10^5$$$) — the number of vertices and the number of edges, respectively.

The second line of each test case contains $$$n$$$ integers $$$c_1, \ldots, c_n$$$ ($$$1 \le c_i \le 3$$$) — Alice's 3-coloring of this graph.

Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — the two vertices that the $$$i$$$-th edge connects. It is guaranteed that there are no self-loops or duplicate edges in the graph.

It is guaranteed that the array $$$c$$$ is a valid $$$3$$$-coloring of the given graph.

Second Run Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Bob.

Each test consists of multiple test cases.

The second line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case consists of three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 3 \cdot 10^5$$$, $$$0 \le k \le \lfloor \frac n 2 \rfloor$$$) — the number of vertices, the number of edges, and the length of the array sent by Alice, respectively.

The second line of each test case contains $$$k$$$ integers $$$a_1, \ldots, a_k$$$ ($$$1 \le a_i \le 3$$$) — the array sent by Alice.

Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — the two vertices that the $$$i$$$-th edge connects. It is guaranteed that there are no self-loops or duplicate edges in the graph.

The graph in both runs is exactly the same, and the edges are given in the same order in both runs.

In both runs of the input, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

Output

First Run Output

For each test case, print two lines.

On the first line, print a single integer $$$k$$$ ($$$0 \le k \le \lfloor \frac n 2 \rfloor$$$) — the size of the array Alice will send to Bob.

On the second line, print $$$k$$$ integers $$$a_1, \ldots, a_k$$$ — Alice's chosen array.

Second Run Output

For each test case, print $$$n$$$ integers $$$b_1, \ldots, b_n$$$ — Bob's $$$3$$$-coloring of the graph. If there are multiple solutions, you may print any.

Examples
Input
first
2
4 4
1 2 3 1
1 2
2 3
1 3
2 4
3 0
1 1 1
Output
2
3 1
1
1
Input
second
2
4 4 2
3 1
1 2
2 3
1 3
2 4
3 0 1
1
Output
3 2 1 1
1 1 1
Note

In the first test case of the first run, Alice has the 3-coloring $$$[1, 2, 3, 1]$$$ and chooses the array $$$a = [3, 1]$$$. Alice's coloring is shown below.

In the second run, Bob receives the array $$$a = [3, 1]$$$. Bob chooses the 3-coloring $$$b = [3, 2, 1, 1]$$$. Bob's coloring is shown below.

I. Ultimate Nim
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Alice and Bob are playing a game. There is a row consisting of $$$n$$$ piles of stones, where the $$$j$$$-th pile contains $$$a_j$$$ stones. On each player's turn, with Alice going first, they remove one stone from any nonempty pile, and the first player who is unable to make a move loses.

However, they have gotten bored with this game, so, inspired by ultimate tic-tac-toe, they have developed a new version, in which there are $$$n$$$ initially identical rows of stones. For example, if $$$a = [3, 0, 1, 4]$$$, the game would initially look like this:

On her first turn, Alice may remove a stone from a pile in any row she chooses, and after that, if the previous player removed from the $$$j$$$-th pile in a row, the current player must choose a pile in the $$$j$$$-th row.

Alice and Bob have both asked you to help them win the game. You must pick which player to assist, and help them win the game.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$)  — the number of rows, as well as the number of piles in each row.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \cdots a_n$$$ ($$$0 \le a_j \le 100$$$), where $$$a_j$$$ is the number of stones in the $$$j$$$-th pile of each of the rows.

It is guaranteed that the sum of $$$n$$$ across all test cases is at most $$$100$$$, and the sum of $$$\sum_{j=1}^n a_j$$$ across all test cases is at most $$$100$$$.

Interaction

After reading in the $$$a_j$$$ values for each test case, print a single line containing either the word Alice or Bob — the name of the player you wish to assist.

After you print this line, the game will begin, with you playing as your chosen player and the judge playing as your opponent.

On each player's turn, they must print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$)  — the row number and pile number from which they will remove a stone. This pile must not be empty, and if it is not the first turn, the $$$i$$$ value printed must match the $$$j$$$ value printed by the previous player.

If the judge has no legal moves on its turn, it will instead print 0 0, indicating that you have won the game, and can proceed to the next test case, or terminate your program if this was the last test case. You must win all test cases to receive the Accepted verdict.

If you remove from an empty pile, or an invalid row, the judge will respond with -1 -1. If you receive this output from the judge, you must terminate your program in order to receive the Wrong Answer verdict. Otherwise, you can receive an arbitrary verdict because your solution is reading from a closed stream.

After printing your chosen player, and after making each of your moves, do not forget to 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
2
1 2


2 2

2 1

0 0
4
0 0 0 0

0 0
Output



Alice
1 2

2 2

1 2



Bob
Note

Here is the sequence of moves in the first test case. Alice's moves are shown in red, and Bob's are shown in blue. In the final step, Bob must remove a stone from a pile in the second row, however these are all empty, so he loses.

In the second test case, all $$$a_j$$$ are zero initially, so Alice is unable to make her first move, and Bob wins.

J. Superset Polygon
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set $$$S$$$ of $$$n$$$ integer lattice points in the plane. Find a simple lattice polygon with no $$$180$$$ degree angles that contains each point in $$$S$$$ as a vertex.

For example, here is an example of the set $$$S$$$ and a valid polygon:

The below polygon would NOT be valid, because of the $$$180$$$ degree angle at $$$(5, 3)$$$.

The polygon must be simple, meaning its edges may only intersect at vertices, and all of its vertices must be at lattice points, but it does not have to be convex, as shown in the example.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 2\cdot10^5$$$) — the number of test cases.

The first line of each test case consists of a single integer $$$n$$$ ($$$1\leq n\leq2\cdot10^5$$$) — the size of $$$S$$$.

The $$$i$$$th of the next $$$n$$$ lines of each test case consists of two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^8\leq x,\,y\leq10^8$$$) — the coordinates of the $$$i$$$-th element of $$$S$$$. It is guaranteed that all points in $$$S$$$ are distinct.

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

Output

The first line of output for each test case should consist of a single integer $$$m$$$ ($$$3\leq m \leq 10\cdot n$$$) — the number of vertices of the polygon. You do not need to minimize $$$m$$$.

The $$$i$$$th of the next $$$m$$$ lines should consist of two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9\leq x_i,\, y_i\leq 10^9$$$) — the coordinates of the $$$i$$$-th vertex of the polygon. All the vertices of $$$S$$$ should be among these.

Under the given input conditions, it can be shown that there exists a solution with the given restrictions on $$$m$$$ and $$$(x_i, y_i)$$$.

If there are multiple solutions, you may print any.

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

The first test case corresponds to the image above.

Here are the points and polygon for the second test case:

K. Grid Coloring
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an $$$n$$$ by $$$m$$$ grid of white squares. You want to color each of these squares either red, green, or blue such that no two squares that share a side are the same color. In addition, there are three special squares in the grid, and no two special squares are allowed to be the same color.

Give a valid coloring or state that none exist.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1000$$$, $$$n\cdot m \ge 3$$$) — the number of rows and columns in the grid, respectively.

Each of the next three lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$) — the position $$$(x, y)$$$ of one of the special squares, where $$$(1, 1)$$$ is the top left corner and $$$(n, m)$$$ is the bottom right corner. It is guaranteed that no two special squares are in the same position.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$1000$$$, and the sum of $$$m$$$ across all test cases does not exceed $$$1000$$$.

Output

For each test case, print YES if there is a solution, and NO otherwise. You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).

If you printed YES, print $$$n$$$ additional lines. The $$$i$$$-th of these should contain $$$m$$$ characters R, G, or B, indicating the colors of the squares in the $$$i$$$-th row of the grid in your coloring.

If there are multiple solutions, you may print any.

Example
Input
4
4 5
1 1
2 4
3 4
1 5
1 2
1 4
1 3
3 3
2 1
3 2
2 3
10 8
1 5
3 7
4 8
Output
YES
RGBRG
GBRGB
BRGBG
GBRGR
YES
RBRGR
NO
YES
RBGBGBRB
GRBRBRBR
RGRGRGRG
GRGBGRGB
RGRGBGBR
BRBRGRGB
RGRGBGBG
BRGRGRGR
RBRBRGBG
BGBRGRGR
Note

The first test case corresponds to the image above.

The second test case uses this coloring:

In the third test case, we can show that there is no solution.

L. MEXpected Value
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given arrays $$$a$$$, $$$p$$$, and $$$q$$$ of $$$n$$$ nonnegative integers each, and a multiset $$$S$$$ that is initially empty. For each $$$1 \le i \le n$$$ in order, you then add $$$a_i$$$ to $$$S$$$ with probability $$$\frac{p_i}{q_i}$$$. What is the expected value of the $$$\operatorname{MEX}$$$ of $$$S$$$ at the end of this process, taken modulo $$$10^9+7$$$?

The $$$\operatorname{MEX}$$$ of a set of integers is defined as the smallest non-negative integer which does not occur in the set. For example, the $$$\operatorname{MEX}$$$ of $$$\{0, 1, 2, 4\}$$$ is $$$3$$$, and the $$$\operatorname{MEX}$$$ of $$$\{1, 4, 6, 8\}$$$ is $$$0$$$.

Input

Each test consists of multiple test cases.

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

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

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$p_i$$$, and $$$q_i$$$ ($$$0 \le a_i \le n$$$, $$$0 \le p_i \le 10^9$$$, $$$\max(1, p_i) \le q_i \le 10^9$$$, $$$p_i$$$ and $$$q_i$$$ are coprime) — $$$a_i$$$ and the two values representing the probability that $$$a_i$$$ is added to $$$S$$$, as described above, respectively.

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 expected $$$\operatorname{MEX}$$$ of $$$S$$$ modulo $$$10^9+7$$$.

Formally, it can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$, where $$$x$$$ and $$$y$$$ are integers and $$$y\not\equiv 0 \mod 10^9+7$$$. Output the integer equal to $$$x\cdot y^{-1}\mod 10^9+7$$$. In other words, output the integer $$$k$$$ such that $$$0\leq k \lt 10^9+7$$$ and $$$k\cdot y\equiv x \mod 10^9+7$$$.

Example
Input
5
1
0 1 3
2
0 1 2
1 1 2
3
0 1 2
0 1 2
0 1 2
6
0 1 4
6 2 7
1 4 9
1 2 5
2 1 1
0 3 5
5
0 1 1
1 4 7
2 3 8
3 19 20
4 0 1
Output
333333336
750000006
875000007
433333338
389285719
Note

In the first test case, we include $$$a_1 = 0$$$ in $$$S$$$ with probability $$$\frac{1}{3}$$$. So $$$\frac{1}{3}$$$ of the time, $$$S = \{0\}$$$, which has a $$$\operatorname{MEX}$$$ of $$$1$$$, and otherwise $$$S = \{\}$$$, with a $$$\operatorname{MEX}$$$ of $$$0$$$.

Therefore the expected value of the $$$\operatorname{MEX}$$$ is $$$\frac{1}{3}$$$, which is $$$333333336$$$ modulo $$$10^9+7$$$.

In the second test case, we include $$$a_1 = 0$$$ in $$$S$$$ with probability $$$\frac{1}{2}$$$ and $$$a_2 = 1$$$ in $$$S$$$ with probability $$$\frac{1}{2}$$$. So there are four possible outcomes for $$$S$$$, each with probability $$$\frac{1}{4}$$$ of occurring:

  • $$$S = \{\}$$$ with a $$$\operatorname{MEX}$$$ of $$$0$$$
  • $$$S = \{0\}$$$ with a $$$\operatorname{MEX}$$$ of $$$1$$$
  • $$$S = \{1\}$$$ with a $$$\operatorname{MEX}$$$ of $$$0$$$
  • $$$S = \{0, 1\}$$$ with a $$$\operatorname{MEX}$$$ of $$$2$$$

So the expected value of the $$$\operatorname{MEX}$$$ is $$$\frac{0 + 1 + 0 + 2}{4} = \frac{3}{4}$$$, which is $$$750000006$$$ modulo $$$10^9+7$$$.

In the third test case, we include $$$a_1 = 0$$$, $$$a_2 = 0$$$, and $$$a_3 = 0$$$ in $$$S$$$ each with independent probability $$$\frac{1}{2}$$$. So there is a $$$\frac{7}{8}$$$ chance that we include at least one of them and the $$$\operatorname{MEX}$$$ of $$$S$$$ is $$$1$$$, and otherwise $$$S$$$ is empty with a $$$\operatorname{MEX}$$$ of $$$0$$$. So the expected value of the $$$\operatorname{MEX}$$$ is $$$\frac{7}{8}$$$, which is $$$875000007$$$ modulo $$$10^9+7$$$.

M. XORzocity
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given constant positive integers $$$k$$$, $$$x$$$, and $$$y$$$. An array $$$a$$$ of size $$$n \gt k$$$ is defined such that:

$$$$$$a_i = \begin{cases} 2^{i-1} & 1 \le i \le k\\ a_{i-x} \oplus a_{i-y} & k \lt i \le n \end{cases}$$$$$$

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to print the binary representation of $$$a_n$$$.

Input

Each test consists of multiple test cases.

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

The first and only line of each test case contains four integers $$$n$$$, $$$k$$$, $$$x$$$, and $$$y$$$ ($$$2 \le n \le 10^{18}$$$, $$$1 \le k \le \min(10^6, n - 1)$$$, $$$1 \le x, y \le k$$$) — the size of the array and the constants described above, respectively.

It is guaranteed that the sum of $$$k$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a binary string of length $$$k$$$ — the binary representation of $$$a_n$$$, with digits in order from most to least significant.

Formally, the $$$i$$$-th character of the string should be 1 if the $$$2^{k-i}$$$ bit of $$$a_n$$$ is set and 0 otherwise.

Example
Input
7
10 6 3 5
123456 1 1 1
2000 7 1 2
12581674 5 5 2
3523686 10 8 8
123456789123456789 8 4 7
500000000000000000 13 11 8
Output
011010
0
1100000
10101
0000000000
00011000
0100001011000
Note

In the first test case, the array $$$a$$$ is $$$[1, 2, 4, 8, 16, 32, 10, 20, 40, 26]$$$. Since $$$26_{10} = 011010_2$$$, we print $$$011010$$$.

In the second test case, the array $$$a$$$ is $$$[1, 0, 0, \cdots 0]$$$.

In the third test case, the array $$$a$$$ is $$$[1, 2, 4, 8, 16, 32, 64, 96, 32, 64, 96, \cdots 32, 64, 96]$$$.

N. Primemas
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Output an integer array $$$a$$$ of length $$$n$$$ such that:

  • $$$1 \le a_i \le 10^9$$$ ($$$1 \le i \le n$$$)
  • For all $$$1 \le j \lt k \le n$$$, $$$a_j + a_k$$$ is a prime number

It can be shown that under the given constraints, a solution always exists.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of a single line containing an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the required length of the array.

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 $$$a_1, \ldots, a_n$$$ satisfying the above constraints.

If there are multiple solutions, you may print any.

Example
Input
2
2
3
Output
6 7
1 66 1
Note

In the first test case, we have $$$a_1 + a_2 = 13$$$, and $$$13$$$ is a prime number.

In the second test case, we have $$$a_1 + a_2 = 67$$$, $$$a_1 + a_3 = 2$$$, and $$$a_2 + a_3 = 67$$$, all of which are prime.