Problem Description

Recently, Little Z became addicted to a new elimination game. The game is played on an $n \times m$ grid. Initially, each cell contains an integer from $0 \sim 9$. After eliminations, blank cells may appear in the grid, denoted by $-1$. For convenience, denote the number in row $i$, column $j$ as $A_{i,j}$, and its coordinate as $(i,j)$.

Given three parameters $l_{\min}, l_{\max}$, and $K$, the player can perform at most $K$ operations. In each operation, the player needs to find a path of length $l$ in the grid. Formally, the path is represented by two sequences of length $l$, $x_1, x_2, \ldots, x_l$ and $y_1, y_2, \ldots, y_l$, satisfying:

1. $1 \le x_i \le n, 1 \le y_i \le m$ for $1 \le i \le l$, i.e., $(x_i,y_i)$ is a valid position in the grid.
2. $\left|x_i-x_{i+1} \right|+ \left|y_i-y_{i+1} \right|=1$ for $1 \le i \lt l$, i.e., $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$ are adjacent cells in the grid.
3. $x_i \neq x_j$ or $y_i \neq y_j$ for $1 \le i \lt j \le l$, i.e., the path cannot pass through any cell more than once.
4. $A_{x_i,y_i} \neq -1$ for $1 \le i \le l$, i.e., the path cannot pass through blank cells.
5. $A_{x_1,y_1} \neq 0$, i.e., the path cannot start with the digit $0$.
6. $l_{\min} \le l \le l_{\max}$, i.e., the path length must be within the given range.

Concatenate the digits along the path into an integer $N$, formally:

$$N=\sum\limits_{i=1}^l A_{x_i,y_i}\times 10^{l-i}$$

The game provides two parameters $c_1, c_2$ to compute the score for this operation:

1. If $N$ is a prime number, you get the prime score $l^{c_1}$; otherwise, the prime score is $1$.
2. If $N$ is a palindrome (i.e., viewing the decimal representation of $N$ as a string, its reverse is exactly the same as itself), you get the palindrome score $l^{c_2}$; otherwise, the palindrome score is $1$.
3. If both the prime score and the palindrome score are $1$, then the score of this operation is $0$. Otherwise, the score of this operation is the sum of the prime score and the palindrome score.

After each operation, if the score of this operation equals $0$, then you waste one operation and the grid does not change. If the score of this operation is greater than $0$, then the numbers on the path are replaced with blanks, and the numbers above blanks fall vertically. Formally, perform the following steps:

1. Set $A_{x_i,y_i}\leftarrow -1$ for $1\le i\le l$.
2. Enumerate all cells. If there exists a cell $(i, j)$ such that $i \neq n$, $A_{i,j} \neq -1$, and $A_{i+1,j} = -1$, then perform $A_{i+1,j} \leftarrow A_{i,j}, A_{i,j}\leftarrow -1$. Repeat this operation until no such cell exists in the grid.

We also provide a parameter $F$. After all operations are completed, the player’s final score $S$ is determined by $F$: if $F=0$, then the final score is the sum of the scores of all operations $m$; if $F=1$, then the final score is the sum of the scores of all operations $m$ divided by $2^d$ and floored, i.e.,

$$S = \begin{cases} m, & F=0\\\\ \left \lfloor \frac{m}{2^d} \right \rfloor, & F=1 \end{cases}$$

where $d$ is the number of non-blank cells in the final grid.

Little Z is so obsessed with this interesting game that she cannot stop. She wants to ask you for help: for the given input parameters, provide an operation plan for the game state. Of course, the higher the final score, the better.

Input Format

This is an output-only problem.

For each input file, line $1$ contains $8$ space-separated integers $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$, with the same meanings as in the statement.

Then follow $n$ lines, each containing $m$ integers, describing the grid $A$. Numbers are separated by one space.

The input file will not contain extra blank lines, and there will be no extra spaces at the end of lines.

Output Format

For the given $10$ input files game1.in ~ game10.in, you need to submit your output files game1.out ~ game10.out respectively.

The first line of the output file is an integer $M \ (0 \leq M \leq K)$, the number of operations you perform.

Then the output file should contain $M$ lines, each describing one operation. For each line, the first integer $l$ indicates the length of the chosen path for this operation. Then follow $2l$ numbers: $x_1, y_1, x_2, y_2, \dots, x_l, y_l$.

The output file should not contain extra spaces or blank lines. Multiple integers on the same line should be separated by one space.

3 3 100 2 3 1 1 0
2 1 1
2 3 3
4 7 1

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

1 3 100 2 3 1 1 1
2 1 1

1
2 1 2 1 3

Hint

Sample Explanation 1

The numbers eliminated in the $4$ eliminations and their corresponding scores are: $37$, score $2+1=3$; $41$, score $2+1=3$; $22$, score $1+2=3$; $131$, score $3+3=6$. The total score is $15$. There may be a better plan.

Sample Explanation 2

This plan contains only one elimination operation. The eliminated number is $11$, and the score for this operation is $2+2=4$. Since $F=1$, the final score is the sum of operation scores $4$ divided by $2^1 = 2$ and floored, which is $2$. If you choose the elimination path $211$, you will get the best possible score for this game state, which is $4$.

Scoring

For each test, we set $9$ scoring parameters $a_{10},a_9, \dots ,a_2$. If your output is invalid, you get $0$ points. Otherwise, if the game score in your solution is $w_{user}$, your score will be given by the table below:

::cute-table{tuack=2}

Score	Condition	Score	Condition
$10$	$w_{user}\ge a_{10}$	$5$	$a_5\le w_{user}\lt a_6$
$9$	$a_9\le w_{user}\lt a_{10}$	$4$	$a_4\le w_{user}\lt a_5$
$8$	$a_8\le w_{user}\lt a_9$	$3$	$a_3\le w_{user}\lt a_4$
$7$	$a_7\le w_{user}\lt a_8$	$2$	$a_2\le w_{user}\lt a_3$
$6$	$a_6\le w_{user}\lt a_7$	$1$	$0\lt w_{user}\lt a_2$

Additional Files

The checker must be compiled and used by yourself.

Please go to Github to download the latest source code of testlib.h.

Translated by ChatGPT 5