P15346 [TOIP 2025] Pancake Stall

Amai set up a stall at a holiday market to sell pancakes. Because everyone eats different amounts, he decided to sell $n$ different pancake sizes. From smallest to largest, they are labeled from $1$ to $n$, and he planned to stack pancakes of the same size into one pile for easy shopping. Each pile can contain at most $m$ pancakes, otherwise it will collapse because it is too tall. Every time Amai finishes cooking a pancake, he puts it on the stall counter. However, because he was too rushed, pancakes of different sizes were stacked together in the same pile. When he noticed, there were already $n$ piles on the counter, each pile had exactly $m$ pancakes, and each size also had exactly $m$ pancakes. Amai wants to use a pancake spatula to move these pancakes and restore the arrangement he originally planned. He can only adjust the pancake positions using the following actions: - Insert the spatula into some pile, between two pancakes. - Move all pancakes above the spatula to the top of another pile (the order of pancakes above the spatula remains unchanged). Because the counter space is limited, besides the existing $n$ piles, the remaining space can only hold one more pile. Also, during the process, no pile may ever exceed $m$ pancakes, otherwise that pile will collapse. Please help Amai rearrange the pancakes so that pancakes of the same size are in the same pile, and smaller pancakes are placed more to the left. For example, if $n=2$, $m=3$, the initial $2$ piles are shown in the figure below (the far right is the remaining empty space on the counter): :::align{center}  ::: One possible sequence of moves is as follows. Insert the spatula into the leftmost pile between the bottom two pancakes, and move them to the remaining empty space on the right: :::align{center}  ::: Insert the spatula into the middle pile between the bottom two pancakes, and move them to the leftmost pile: :::align{center}  ::: Move the top pancake of the leftmost pile to the middle pile: :::align{center}  ::: Then move the two pancakes in the rightmost pile to pile $1$ and pile $2$ respectively, and Amai’s desired arrangement is completed: :::align{center}  ::: Please write a program to help Amai move pancakes of various sizes to the desired positions. Since there can be many valid ways to move them, you may output any feasible sequence of moves, but the number of moves must be within $9nm$.

$$ \begin{aligned} &m \; n \\ &a_{1,1} \; a_{1,2} \; \cdots \; a_{1,m} \\ &a_{2,1} \; a_{2,2} \; \cdots \; a_{2,m} \\ &\vdots \\ &a_{n,1} \; a_{n,2} \; \cdots \; a_{n,m} \end{aligned} $$ * $n$ means there are currently $n$ piles of pancakes. * $m$ means each pile currently has exactly $m$ pancakes, and each pancake size also has exactly $m$ pancakes. * $a_{i,j}$ means the size of the $j$-th pancake (from bottom to top) in the $i$-th pile (from left to right).

$$ \begin{aligned} &c \\ &s_1 \; k_1 \; t_1 \\ &s_2 \; k_2 \; t_2 \\ &\vdots \\ &s_c \; k_c \; t_c \end{aligned} $$ * $c$ is the total number of moves. * $s_i$, $k_i$, $t_i$ mean that in the $i$-th move, the top $k_i$ pancakes are moved from the $s_i$-th pile (from left to right) to the $t_i$-th pile (from left to right). (Pile $n+1$ is the empty space at the beginning.) * $0 \le c \le 9nm$. * $1 \le s_i, t_i \le n+1$, and $s_i \neq t_i$. * $k_i \ge 1$ and must not exceed the current number of pancakes in pile $s_i$.

### Constraints * $1 \le n \le 50$. * $1 \le m \le 50$. * $1 \le a_{i,j} \le n$. * All input numbers are integers. * It is guaranteed that each number from $1$ to $n$ appears exactly $m$ times in $a$. ### Scoring This problem has three subtasks, with restrictions as follows. Each subtask may contain one or more testdata, and the score of the subtask is the minimum score among all its testdata. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 8 | $m = 1$。 | | 2 | 37 | $n = 2$。 | | 3 | 55 | No additional constraints. | For this problem, if you output any valid solution for a testdata, you will receive full score for that testdata. However, if your output has any of the following invalid cases, that testdata will receive $0$ points: - The number of moves is too large. - Numbers are out of range. - The number of moved pancakes is greater than the number of pancakes in the source pile. - After all moves, pancakes of size $i$ are not all in pile $i$. In addition, if during the moving process any pile ever exceeds $m$ pancakes, then that testdata will be scored as $30\%$ of the original score for the testdata group. Translated by ChatGPT 5