You are given an integer $$$n$$$. Find the largest set of distinct binary strings of length $$$n$$$ such that no two strings in the set differ at exactly one index.
For example, for $$$n=5$$$, the strings $$$10001$$$ and $$$11001$$$ could not both be in the set, because they only differ in their second positions.
The first and only line of the input contains one integer $$$n$$$ ($$$1 \leq n \leq 15$$$) — the size of the binary strings in the set.
The first line of output should contain a single integer $$$k$$$ ($$$0 \leq k \leq 2^n$$$) — the number of strings in your set.
Each of the next $$$k$$$ lines should contain a single binary string of size $$$n$$$ — one of the strings in your set. No two of these strings should be equal, or differ in exactly one position.
If there are multiple solutions, you may print any.
1
1 0
2
2 00 11
In the first sample case, we choose the set $$$\{0\}$$$, and in the second sample case, we choose the set $$$\{00, 11\}$$$. Neither of these sets contain two strings that differ in exactly one position, and we can show that they are both of maximal size for their given $$$n$$$.
There are $$$n$$$ stones in a row, each marked with $$$L$$$ or $$$R$$$. You can jump from an $$$L$$$ stone to any stone to its left, and from an $$$R$$$ stone to any stone to its right.
More formally, for a stone at position $$$1 \le i \le n$$$, if it is marked with $$$L$$$, you can jump to any stone $$$j$$$ where $$$1 \le j \lt i$$$, and if it is marked with $$$R$$$, you can jump to any stone $$$j$$$ where $$$i \lt j \le n$$$.
Your goal is to find a sequence of jumps such that you visit every stone exactly once. If you can start at any stone of your choice, is this possible?
One example of a valid path visiting each stone once, starting from the second stone The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. 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 number of stones.
The next line of each test case contains a string $$$s$$$ consisting of $$$n$$$ characters L and R, indicating whether stone $$$i$$$ is marked with $$$L$$$ or $$$R$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case print "YES" (without quotes) if it is possible, and "NO" (without quotes) 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).
76LRRLRL1L2RL2LR5RRRRL10LRLRLRLRLR31LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
YES YES YES NO YES NO YES
In the second sample case, $$$n=1$$$, so you can start on the first stone, at which point you have visited all stones and completed your path.
In the fourth sample case, it can be shown that no valid path exists.
Maxwell is renovating his bathroom and wants to redo the tiling on his wall. His wall is a $$$2m \times 2n$$$ rectangle. To describe the placement of tiles on the wall, we will use a coordinate system placing the center at the origin, so that the wall is described by the rectangle with vertices $$$(m, n)$$$, $$$(m, -n)$$$, $$$(-m, -n)$$$, and $$$(-m, n)$$$. For example, for $$$m=3$$$, $$$n=2$$$, his wall would look like this:
Maxwell wishes to tile his wall using tiles shaped like connected polyominoes (https://en.wikipedia.org/wiki/Polyomino) formed from $$$1 \times 1$$$ squares, but he has special conditions on how he wants them to be placed. A tile is well-placed if the value of $$$\max(|x|, |y|)$$$ is constant across all the centers of the squares making up that tile. These tiles are allowed to have "holes" in the middle, as long as the tile itself is one connected group.
For example, one possible well-placed tiling of the above wall would be:
How many ways can Maxwell tile his bathroom wall with well-placed tiles? Two configurations of tiles are considered different if two squares are part of the same tile in one configuration but are part of different tiles in the other.
Since the answer may be very large, print it modulo $$$10^9 + 7$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
Each test case consists of a single line containing two integers $$$m$$$ and $$$n$$$ ($$$1 \le m, n \le 10^6$$$) — the parameters above, describing the dimensions of Maxwell's wall.
Note that there is no additional constraint on the sum of $$$n$$$ or $$$m$$$ across all test cases.
For each test case, output a single integer — the number of ways Maxwell can tile his wall with well-placed tiles, modulo $$$10^9 + 7$$$.
41 13 12 35 4
12 192 3136512 734798461
Here are the 12 possible tilings for the first sample case:
You are given a set $$$S$$$ of $$$n$$$ distinct integers. You will also receive $$$q$$$ queries, each of one of the following two types:
- Query Type 1 $$$(1\; x)$$$:
- If $$$x$$$ is currently in the set $$$S$$$, remove it.
- Otherwise, add $$$x$$$ to the set.
- Query Type 2 $$$(2\; t)$$$:
- Print the cumulative bitwise XOR of $$$(x + t)$$$ over all $$$x \in S$$$. Formally, print $$$\displaystyle\bigoplus_{x \in S} (x + t)$$$.
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 3 \cdot 10^5$$$) — the initial size of the set and the number of queries, respectively.
The next line of the input will contain $$$n$$$ distinct integers $$$x_1, x_2 \cdots x_n$$$ ($$$0 \le x_i \lt 2^{20}$$$) — the initial set.
The next $$$q$$$ lines of the input will describe the queries. Each of them will contain a query of the form $$$1\; x$$$ or $$$2\; t$$$ ($$$0 \le x, t \lt 2^{20}$$$), representing the query in the format described above.
It is guaranteed that there is at least one query of type $$$2$$$.
For each query of type $$$2$$$, print the cumulative bitwise XOR of $$$(x+t)$$$ over all $$$x \in S$$$.
3 101 6 152 01 51 61 102 32 121 152 71 02 7
8 19 17 21 18
In the sample case, at the time of the first type $$$2$$$ query, we have $$$S = \{1, 6, 15\}$$$. Since $$$t = 0$$$ for this query, we print the value $$$$$$(1 + 0) \oplus (6 + 0) \oplus (15 + 0) = 1 \oplus 6 \oplus 15 = 8$$$$$$ At the time of the second type $$$2$$$ query, we have $$$S = \{1, 5, 10, 15\}$$$. Since $$$t = 3$$$ for this query, we print the value $$$$$$(1 + 3) \oplus (5 + 3) \oplus (10 + 3) \oplus (15 + 3) = 4 \oplus 8 \oplus 13 \oplus 18 = 19$$$$$$
You are playing the new hit computer game, "1D Super Checkers Solitaire"!
The game is played on a number line. Initially, a white token is placed at position $$$-1$$$, and $$$n$$$ black tokens are placed at distinct positions $$$x_1, x_2, \dots, x_n$$$ (with $$$1 \le x_i \le 10^9$$$). Note that position $$$0$$$ will never initially contain a token of either color. There is also a score counter, $$$s$$$, which is initially $$$0$$$.
On each turn, you move a black token one step to the left, under the restriction that tokens cannot overlap.
After each of your moves, the computer, playing the white token, repeats the following process while there is a black token immediately to the right of the white token:
- Let $$$i$$$ be the current position of the white token, and let $$$k$$$ be the number of contiguous black tokens starting at position $$$i+1$$$ (i.e., tokens at positions $$$i+1, i+2, \dots, i+k$$$, with position $$$i+k+1$$$ empty).
- The white token jumps over and removes these $$$k$$$ black tokens, landing at position $$$i+k+1$$$.
- The score counter is updated to $$$s = s \oplus k$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).
Finally, you regain control, and can take another turn if there are black tokens remaining.
Here is an example turn. The board could initially look like this:
You could choose to move a black token from position $$$1$$$ to position $$$0$$$, resulting in this configuration:
The computer would then repeatedly jump over the ranges of black tokens next to it, ending up at position $$$6$$$:
After these moves, the score would become $$$0 \oplus 1 \oplus 2 \oplus 1 = 2$$$, and the game would continue, since there are more black tokens remaining.
The game ends when there are no more black tokens.
At the end of the game, you win only if and only if $$$s$$$ is equal to $$$0$$$. Determine whether you can win if you play optimally.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. 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 number of black tokens.
The second line of each test case contains $$$n$$$ integers $$$x_1 \lt x_2 \lt \cdots, x_n$$$ ($$$1 \le x_i \le 10^9$$$) — the initial positions of the black tokens, in strictly increasing order.
For each test case, print "YES" if you can win if you play optimally, or "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
361 2 4 5 7 81456101 4 5 6 7 10 11 12 13 14
YES NO YES
In the first sample case, one winning move you can make is moving a black piece from position $$$1$$$ to position $$$0$$$.
The computer will then jump over all $$$4$$$ consecutive groups of your pieces, and the score will be set to $$$0 \oplus 1 \oplus 1 \oplus 1 \oplus 2 \oplus 2 = 0$$$:
Since there are no remaining black tokens, the game ends, and since $$$s = 0$$$, you win.
In the second sample case, since $$$n=1$$$, the score will always be $$$s = 1$$$ at the end of the game, and you will lose.
You are given an undirected graph where each edge is colored either red or blue. We define a string $$$s$$$ consisting of characters $$$\texttt{R}$$$ and $$$\texttt{B}$$$ to be walkable if there exists a path in the graph where the colors of the edges in the path match the characters of $$$s$$$ in order. The path is not required to be simple, so it is allowed to visit edges and vertices multiple times.
For example, consider the below graph:
In this case, the string $$$\texttt{BRRBB}$$$ is walkable, because you can use this path:
Find a non-walkable string of minimum length or determine that all strings are walkable.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$0 \le m \le 2\cdot 10^5$$$) — the number of vertices and edges in the graph, respectively.
Each of the next $$$m$$$ lines of the input describes an edge of the graph. It contains two integers $$$u$$$ and $$$v$$$, and a character $$$c$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$c = \texttt{B}$$$ or $$$\texttt{R}$$$) — the endpoints of the edge and its color. It is guaranteed that there is at most one edge between each unordered pair of vertices.
It is guaranteed that the sum of $$$n$$$ across all test cases is at most $$$2\cdot 10^5$$$, and the sum of $$$m$$$ across all test cases is at most $$$2\cdot 10^5$$$.
For each test case, print a single line containing a minimum-length non-walkable string, or $$$-1$$$ if all strings are walkable.
If there are multiple answers, you may print any.
54 41 2 B3 1 B3 4 R4 1 R3 31 2 R2 3 R3 1 R4 21 2 R3 4 B7 101 2 B1 4 R2 4 B4 5 B6 7 R6 2 R5 7 B3 6 B3 7 R1 7 B3 0
BRB B RB -1 R
The graph in the first sample case corresponds to the picture above. It can be shown that all strings of length 2 or less are walkable on this graph.
The graph in the second sample case contains no blue edges, so the string $$$\texttt{B}$$$ is not walkable.
It can be shown that all strings are walkable on the graph in the fourth sample case.
An array $$$a$$$ of size $$$n$$$ is considered $$$k$$$-regular if every subarray of $$$a$$$ of size $$$k$$$ contains all integers from $$$1$$$ to $$$k$$$, inclusive.
For example, $$$a = [2, 1, 3, 2]$$$ is $$$3$$$-regular, because its two subarrays of size $$$3$$$ are $$$[2, 1, 3]$$$ and $$$[1, 3, 2]$$$, each of which contains all integers from $$$1$$$ to $$$3$$$. On the other hand, $$$a = [1, 2, 3, 4]$$$ is not $$$3$$$-regular because the subarray $$$[2, 3, 4]$$$ of size $$$k=3$$$ does not contain $$$1$$$.
Your task is to find a $$$k$$$-regular array $$$a$$$ of size $$$n$$$ such that the sum of its elements is maximized.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
Each test case consists of a single line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2\cdot 10^5$$$) — the desired size of the array $$$a$$$, and the parameter $$$k$$$ described above.
It is guaranteed that the sum of $$$n$$$ across all test cases is at most $$$2\cdot 10^5$$$.
For each test case, output a single line containing $$$n$$$ integers $$$a_1, a_2, \cdots a_n$$$ — a $$$k$$$-regular array $$$a$$$ of size $$$n$$$ with maximal sum.
If there are multiple solutions, you may print any.
44 35 13 21 1
3 1 2 3 1 1 1 1 1 2 1 2 1
In the first sample case, the array $$$a = [3, 1, 2, 3]$$$ is $$$3$$$-regular because its two subarrays of size $$$3$$$ are $$$[3, 1, 2]$$$ and $$$[1, 2, 3]$$$, each of which contains all integers from $$$1$$$ to $$$3$$$. The sum of this array is $$$3 + 1 + 2 + 3 = 9$$$, which we can show is maximal for this $$$n$$$ and $$$k$$$.
In the second sample case, each subarray of size $$$1$$$ must contain $$$1$$$, and therefore, the array must consist only of ones.
This problem has an interactive web tool that lets you test the painting process for yourself!
You have a canvas that is represented as a $$$2$$$ by $$$n$$$ grid, and a cube with the same side length as the squares in the canvas. You want to paint the canvas using the cube, so you begin by painting each of the faces of the cube in a different color, as shown here:
Note that this coloring is fixed, so for example, the red face must always be opposite the blue face, etc.
You will paint the canvas by first placing the cube, with any face of your choice facing down, on any square of the canvas. You can then repeatedly "roll" the cube along any of the edges currently touching the canvas. Any time a face of the cube touches a square of the canvas, that square is painted the same color as the face. For example, here is one possible sequence of $$$5$$$ moves you could make:
After this sequence of moves, the canvas would look like this:
If two colors mix, the resulting color is very ugly, so you don't want to use it in your painting. Therefore, once you've painted a square, you aren't allowed to move the cube in a way that would paint that square again in a different color. Note that painting a square the same color multiple times is fine, as shown by the red square in the example above.
You want to make the canvas as colorful as possible, so you don't want any white squares to remain once the painting is done.
Under these restrictions, how many distinct paintings are possible? Two paintings are considered distinct if there exists a square on the canvas that is painted in different colors in each. Since the answer may be large, print it modulo $$$10^9+7$$$.
A web tool is available that lets you move the cube around and paint the canvas.
It can be found here: https://joedurie.github.io/cubist-painting-web-tool/
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.
Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the number of columns in the canvas.
For each test case, output a single integer — the number of distinct paintings on a $$$2$$$ by $$$n$$$ canvas, modulo $$$10^9+7$$$.
71234510001000000000000000000
24 96 312 1056 3408 152353512 86193561
Here are the $$$24$$$ possible paintings for the first sample case:
Alice and Bob are playing a game on a $$$1 \times n$$$ board. On her turn, Alice places a $$$1 \times a$$$ tile on the board, while on his turn, Bob places a $$$1 \times b$$$ tile. Tiles must be placed on unoccupied cells and cannot overlap.
Whoever cannot make a move loses.
Alice moves first, and to compensate for the advantage of going first, Alice's pieces are larger than Bob's (in other words, $$$a \gt b$$$). Given three integers $$$a$$$, and $$$b$$$ , $$$n$$$, determine who will win the game if both players play optimally.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.
Each of the next $$$t$$$ lines contains three space-separated integers $$$a$$$, $$$b$$$, and $$$n$$$ ($$$1 \le b \lt a \le n \le 10^9$$$) — the sizes of the tiles used by Alice and Bob, and the length of the board, respectively.
For each test case, print "Alice" if Alice wins the game, or "Bob" if Bob wins.
310 1 105 1 107 4 20
Alice Bob Bob
In the first sample, since Alice goes first and $$$a = n = 10$$$, she can fill in the entire board on her first move, and Bob will not have any legal moves, losing the game.
In the second sample, Alice can never stop Bob from placing a piece on his first turn. After Bob's first turn, there will only be $$$4$$$ empty squares in total, so Alice can never place a piece on her second turn and will lose the game.
You are given an array $$$a$$$ of $$$n$$$ integers. You then perform the following process $$$k$$$ times.
- Choose an integer $$$i$$$ where $$$1 \le i \le n$$$, uniformly at random.
- For each $$$1 \le j \le n$$$, move $$$a_j$$$ one unit closer to $$$a_i$$$. Formally, for each $$$j$$$,
- If $$$a_j \lt a_i$$$, increment $$$a_j$$$ by $$$1$$$
- If $$$a_j \gt a_i$$$, decrement $$$a_j$$$ by $$$1$$$
- If $$$a_j = a_i$$$, do not modify the value of $$$a_j$$$.
After performing this process $$$k$$$ times, you select an integer $$$i$$$ where $$$1 \le i \le n$$$ uniformly at random. What is the expected value of $$$a_i$$$?
It can be shown that this value can be represented as $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \mod 10^9+7$$$. Print the value of $$$P\cdot Q^{-1}$$$ modulo $$$10^9+7$$$.
The first line of the 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,k \le 2\cdot 10^5$$$) — the length of the array and the number of operations you will perform.
The second line of each test case will contain $$$n$$$ integers $$$a_1, a_2, \cdots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases, and the sum of $$$k$$$ over all test cases, do not exceed $$$2\cdot 10^5$$$.
For each test case, output a single line containing the expected value of $$$a_i$$$ at the end of this process, modulo $$$10^9+7$$$ as described above.
33 58 8 82 110 117 79 8 7 6 5 4 2
8 500000014 857142869
In the first sample case, since all elements of $$$a$$$ are initially equal, none of them will change after any of the $$$k=5$$$ operations. Therefore, the final array will be $$$[8, 8, 8]$$$, so the expected value of a random element of the final array is $$$8$$$.
In the second sample case, there is a $$$50\%$$$ chance of choosing $$$i = 1$$$ in the operation, and a $$$50\%$$$ chance of choosing $$$i = 2$$$.
- If $$$i = 1$$$ is chosen, all elements of the array will move closer to $$$a_1 = 10$$$, so $$$a$$$ will go from $$$[10, 11]$$$ to $$$[10, 10]$$$. The expected value of a random element of this array is $$$10$$$.
- If $$$i = 2$$$ is chosen, all elements of the array will move closer to $$$a_2 = 11$$$, so $$$a$$$ will go from $$$[10, 11]$$$ to $$$[11, 11]$$$. The expected value of a random element of this array is $$$11$$$.
So there is a $$$50\%$$$ chance of the expected value being $$$10$$$, and a $$$50\%$$$ chance of it being $$$11$$$. Therefore, the final expected value is $$$10.5 = \frac{21}{2}$$$, which is equivalent to $$$5000000014$$$ modulo $$$10^9+7$$$.
You are given a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Each node $$$u$$$ has an ordered list $$$l_u$$$ of its neighbors, and an arrow pointing to one of its neighbors $$$p_u$$$. Initially, $$$p_u$$$ is the first neighbor in $$$l_u$$$.
You start at node $$$s$$$, and repeat the following process infinitely many times:
- Let $$$v$$$ be the node at which you are currently located. Move from $$$v$$$ to $$$p_v$$$.
- Increment $$$p_v$$$ to the next neighbor in $$$l_v$$$ cyclically.
See the sample notes for an example of this process.
Consider the list $$$p_1, p_2, \cdots p_n$$$ over the course of this process, as well as the current node $$$c$$$. We call this a "state".
Print any state that appears an infinite amount of times.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 4 \cdot 10^5$$$, $$$1 \le s \le n$$$) — the number of vertices and edges in the graph, and the starting node, respectively.
The $$$u$$$-th of the next $$$n$$$ lines describes the ordered list $$$l_u$$$ of neighbors of $$$u$$$. It begins with an integer $$$k_u$$$ ($$$1 \le k_u \lt n$$$) — the number of neighbors of $$$u$$$. This is followed by $$$k_u$$$ distinct integers $$$v_1, v_2, \cdots v_{k_u}$$$ ($$$1 \le v_i \le n$$$, $$$v_i \ne u$$$) — the neighbors of $$$u$$$.
It is guaranteed that if $$$v$$$ is a neighbor of $$$u$$$, then $$$u$$$ is a neighbor of $$$v$$$. It is also guaranteed that there are $$$m$$$ undirected edges in total.
Across all test cases, it is guaranteed that the sum of $$$n$$$ is at most $$$2 \cdot 10^5$$$, and the sum of $$$m$$$ is at most $$$4 \cdot 10^5$$$.
For each test case print any state that repeats infinitely in the format $$$c$$$ $$$p_1$$$ $$$p_2$$$ $$$...$$$ $$$p_n$$$.
34 3 21 41 32 4 22 3 14 3 31 41 32 4 22 3 14 4 12 4 22 1 32 2 42 3 1
3 4 3 2 1 3 4 3 2 1 1 4 1 2 3
Let's visualize the third sample case. The red node represents your current position, and the arrow pointing out from each node $$$u$$$ points at node $$$p_u$$$. Here is how the graph looks at the start of the process, and after each of the next $$$8$$$ steps:
We can see that after $$$8$$$ operations have been performed, we have reached the initial state $$$p_1 = 4, p_2 = 1, p_3 = 2, p_4 = 3$$$ once again, and our current location (node $$$1$$$) is the same as it was at the beginning. Therefore, a valid answer is to simply print the initial state.
There are two hidden permutations $$$a$$$ and $$$b$$$ of size $$$n$$$.
A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1, 3, 4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
For each $$$i$$$ from $$$1$$$ to $$$n$$$, you are given the values $$$a_{b_i}$$$ and $$$b_{a_i}$$$. Recover any possible permutations $$$a$$$ and $$$b$$$, or determine that none exist.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. 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 size of the two permutations.
The second line of each test case contains $$$n$$$ integers. The $$$i$$$-th of these is $$$a_{b_i}$$$ ($$$1 \le a_{b_i} \le n$$$). It is guaranteed that these $$$n$$$ integers are distinct.
The third line of each test case contains $$$n$$$ integers. The $$$i$$$-th of these is $$$b_{a_i}$$$ ($$$1 \le b_{a_i} \le n$$$). It is guaranteed that these $$$n$$$ integers are distinct.
It is guaranteed that the sum of $$$n$$$ across all test cases is at most $$$2\cdot 10^5$$$.
For each test case, the first line of output should contain "YES" if there is a solution, and "NO" otherwise. You can print this in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
If you print "YES", print two additional lines of output:
The first line should contain $$$n$$$ integers $$$a_1, a_2, \cdots a_n$$$ ($$$1 \le a_i \le n$$$) — a valid permutation $$$a$$$.
The second line should contain $$$n$$$ integers $$$b_1, b_2, \cdots b_n$$$ ($$$1 \le b_i \le n$$$) — a valid permutation $$$b$$$.
If there are multiple solutions, you may print any.
633 1 22 3 121 22 151 2 3 4 51 2 3 4 511164 5 1 2 3 61 2 3 4 5 6103 7 5 8 9 1 4 10 6 27 8 1 5 10 9 2 3 4 6
YES 2 1 3 3 2 1 NO YES 5 4 3 2 1 5 4 3 2 1 YES 1 1 NO YES 8 2 4 6 1 5 10 7 9 3 10 8 6 1 9 5 3 7 4 2
The given solution to the first sample case is $$$a=[2, 1, 3]$$$, $$$b=[3, 2, 1]$$$. This gives $$$$$$a_{b_1} = a_3 = 3 \quad\quad a_{b_2} = a_2 = 1 \quad\quad a_{b_3} = a_1 = 2$$$$$$ $$$$$$b_{a_1} = b_2 = 2 \quad\quad b_{a_2} = b_1 = 3 \quad\quad b_{a_3} = b_3 = 1$$$$$$ which matches the input values $$$a_b=[3, 1, 2]$$$ and $$$b_a=[2, 3, 1]$$$.
In the second sample case, it can be shown that there are no valid permutations $$$a$$$ and $$$b$$$.
Define a number $$$b$$$ to be a subsequence of a number $$$a$$$ if, when you write out $$$a$$$ in decimal notation, you can erase some (but not all) of its digits so that the remaining digits, in order, form $$$b$$$. For example, $$$356$$$ is a subsequence of $$$1234567$$$, because you can erase the $$$1$$$, $$$2$$$, $$$4$$$, and $$$7$$$ to form $$$356$$$. However, $$$0$$$ is not a subsequence of $$$23527$$$, because the digit $$$0$$$ is not present in $$$23527$$$.
You are given a number $$$x$$$. Find any number $$$n$$$ such that the $$$\operatorname{MEX}$$$ of the set of all subsequences of $$$n$$$ is equal to $$$x$$$. It can be shown that such an $$$n$$$ always exists.
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$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.
Each test case consists of a single line containing an integer $$$x$$$ ($$$1 \le x \lt 10^{10000}$$$) — the desired $$$\operatorname{MEX}$$$ of the subsequences of $$$n$$$. It is guaranteed that $$$x$$$ does not contain any leading zeroes.
It is guaranteed that the sum of the number of digits of $$$x$$$ across all test cases is at most $$$10000$$$.
For each test case, output a single positive integer $$$n$$$ — any number such that the $$$\operatorname{MEX}$$$ of its subsequences is $$$x$$$. $$$n$$$ may not contain leading zeroes.
If there are multiple solutions, you may print any.
The sum of the number of digits of $$$n$$$ across all test cases must not exceed $$$10^6$$$.
4191022
70 12836880457 2468013579 12013456789
In the first sample case, the subsequences of $$$70$$$ are $$$7$$$, $$$0$$$, and $$$70$$$, and the $$$\operatorname{MEX}$$$ of $$$\{0, 7, 70\}$$$ is $$$1$$$.
In the second sample case, $$$12836880457$$$ contains every digit except $$$9$$$, and therefore the $$$\operatorname{MEX}$$$ of its subsequences is $$$9$$$.
Thomas wants to buy $$$n$$$ cups of ramen from Liza. She has two brands that he likes: brand A and brand B. Each brand sells packs of ramen in varying sizes. For each integer $$$k \ge 1$$$, there is a brand A pack of size $$$k$$$ that contains $$$k^2$$$ cups of ramen, and a brand B pack of size $$$k$$$ that contains $$$2k^2$$$ cups of ramen. Liza has exactly one pack of each type left in stock. Your task is to determine how Thomas can purchase exactly $$$n$$$ cups of ramen from Liza, or state that such a thing is not possible.
Note that you do not need to minimize the number of packs.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.
Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$), the number of ramen cups that Thomas wants from Liza.
For each test case, output a single line.
If it is not possible for Thomas to buy $$$n$$$ cups of ramen from Liza, simply print $$$0$$$.
Otherwise, print a positive integer $$$k$$$, followed by a list of $$$k$$$ pack types. A pack type is a letter (either A or B) indicating the brand of the ramen pack followed by a positive integer indicating its size. The sum of the number of cups over all packs should be $$$n$$$, and no pack type may appear more than once.
41101220
1 A1 2 A1 A3 2 A2 B2 4 A3 B2 B1 A1
In the first test case, Thomas buys just the $$$A1$$$ pack from Liza for a total of $$$1^2 = 1$$$ cups.
In the second test case, Thomas can buy the $$$A1$$$ and $$$A3$$$ packs from Liza for a total of $$$1^2 + 3^2 = 10$$$ cups.
In the third test case, Thomas can buy the $$$A2$$$ and $$$B2$$$ packs from Liza for a total of $$$2^2 + 2*2^2 = 12$$$ cups.
In the fourth test case, Thomas can buy the $$$A3$$$, $$$B2$$$, $$$B1$$$, and $$$A1$$$ packs from Liza for a total of $$$3^2 + 2*2^2 + 2*1^2 + 1^2 = 20$$$ cups.