Problem Description

$\textit{Chomp!}$ is a classic two-player game. At the start, there is a whole chocolate bar made of $mn$ small $1 \times 1$ squares, arranged like an $m \times n$ 2D array (where $m$ is the number of rows and $n$ is the number of columns). The bottom-left square is extremely bitter, and everyone wants to avoid it. The game is played by taking turns removing chocolate squares: on each turn, a player picks one remaining square, and removes it together with all squares to its upper-right (including those directly above it and directly to its right). In the end, whoever takes the bottom-left square loses.

For example, initially there is a $3 \times 4$ chocolate bar:

:::align{center} :::

If Player 1 chooses the square $X$, then the squares marked $Y$ will also be removed:

:::align{center} :::

Then Player 2 chooses from the remaining chocolate squares. If Player 2 now chooses the square $W$, then the squares marked $Z$ will also be removed:

:::align{center} :::

Following the rules above, it is not hard to prove that any position that can appear in the game, when described by listing from left to right the number of remaining chocolate squares in each column, must be a monotonic decreasing sequence, and this sequence uniquely determines the shape. For the final state in the example above, it can be represented by the sequence $(3, 1, 0, 0)$.

In this problem, we analyze various positions that appear in the $\textit{Chomp!}$ game on a $3 \times n$ chocolate bar, with the goal of determining whether the first player has a winning move in the current position. We assume both players are perfectly smart and will use the best strategies to win. If the first player can win, output how many winning choices there are for the first move, and enumerate these choices; otherwise, output $0$. Here, we label the chocolate square in the $i$-th row from the bottom and the $j$-th column from the left as $(i, j)$, with the bottom-left corner being $(1, 1)$ and the top-right corner being $(3, n)$.

Input Format

$$\begin{aligned} &t \\ &n_1 \; p_1 \; q_1 \; r_1 \\ &\vdots \\ &n_t \; p_t \; q_t \; r_t \end{aligned}$$

• $t$ is the total number of queries.
• $n_i$ is the total number of columns of the chocolate bar in the $i$-th query.
• $p_i, q_i, r_i$ describe the position in the $i$-th query: from left to right, the first $p_i$ columns have $3$ chocolate squares, then the next $q_i$ columns have $2$ chocolate squares, and then the next $r_i$ columns have $1$ chocolate square.

Output Format

$$\begin{aligned} &c_1 \\ &x_{1,1} \; y_{1,1} \; \dots \; x_{1,c_{1}} \; y_{1,c_{1}} \\ &\vdots \\ &c_t \\ &x_{t,1} \; y_{t,1} \; \dots \; x_{t,c_{t}} \; y_{t,c_{t}} \end{aligned}$$

• $c_i$ is the number of first-move choices that allow the first player to win in the position of the $i$-th query. If the first player cannot win, then $c_i = 0$.
• $x_{i,j}, y_{i,j}$ are the coordinates of the $j$-th winning first-move choice (a chocolate square) in the $i$-th query. If $c_i > 1$, sort the coordinates by increasing $x$, and if $x$ is the same, by increasing $y$.

4
1 0 0 1
10 1 0 9
3 1 2 0
3 1 1 1

0
1
1 4
2
1 3 2 2
3
1 3 2 2 3 1

1
100 67 22 11

3
1 100 2 59 3 18

Hint

Constraints

• $1 \le t \le 1000$.
• $1 \le n_i \le 500$.
• $0 \le p_i, q_i, r_i \le n_i$.
• $1 \le p_i + q_i + r_i \le n_i$.
• All input values are integers.

Scoring

This problem has three subtasks, with constraints as listed below. Each subtask may contain one or more testdata files. You will get the score for a subtask only if you pass all testdata in that subtask.

Subtask	Score	Additional Input Constraints
1	20	$t = 1$, $p_i = 0$.
2	37	$1 \le n_i \le 50$.
3	43	No additional constraints.

Translated by ChatGPT 5