Problem Description

Recently, Xiao Z has become obsessed with a new type of elimination game. The game takes place on a grid of size $n \times m$, initially filled with integers from $0$ to $9$. After eliminations, the grid will have blanks, represented by $-1$. We denote the number in the $i$-th row and $j$-th column as $A_{i,j}$, and its coordinates as $(i,j)$.

Given three parameters $l_{\min}, l_{\max}$, and $K$, the player can perform no more than $K$ operations. For each operation, the player needs to find a path of length $l$ in the grid. Formally, this 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 the following conditions:
1. $1 \le x_i \le n, 1 \le y_i \le m$ for $1 \le i \le l$, meaning $(x_i, y_i)$ is a valid position on the grid;
2. $|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$ for $1 \le i < l$, meaning $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ are adjacent positions;
3. $x_i \neq x_j$ or $y_i \neq y_j$ for $1 \le i < j \le l$, meaning the path does not repeat any grid cell;
4. $A_{x_i, y_i} \neq -1$ for $1 \le i \le l$, meaning the path does not pass through blank cells;
5. $A_{x_1, y_1} \neq 0$, meaning the path does not start with the number $0$;
6. $l_{\min} \le l \le l_{\max}$, meaning the path length is within the given range.

The numbers on the path form an integer $N$, defined as
$$ N = \sum_{i=1}^l A_{x_i, y_i} \times 10^{l-i} $$

The game provides two parameters $c_1, c_2$ to calculate the score for each operation:
1. If $N$ is a prime number, the prime score is $l^{c_1}$, otherwise it is $1$;
2. If $N$ is a palindrome (i.e., the decimal representation of $N$ reads the same backward as forward), the palindrome score is $l^{c_2}$, otherwise it is $1$;
3. If both the prime score and palindrome score are $1$, the operation score is $0$; otherwise, the operation score is the sum of the prime score and palindrome score.

After each operation, if the operation score is $0$, the player has wasted an operation, and the grid remains unchanged. If the operation score is greater than $0$, the numbers on the path are replaced by blanks, and the numbers above the blanks fall vertically. Formally, perform the following operations:
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$, perform $A_{i+1, j} \leftarrow A_{i, j}$, $A_{i, j} \leftarrow -1$. Repeat this operation until no such cells exist.

A parameter $F$ is also given. After all operations, the player's final score $S$ is determined by $F$: if $F$ is $0$, the final score is the sum of all operation scores $m$; if $F$ is $1$, the final score is the sum of all operation scores $m$ divided by $2^d$ and rounded down, where $d$ is the number of non-blank cells in the final grid.

Xiao Z is deeply immersed in this fascinating game and wants your help to devise strategies for the given input parameters, aiming for the highest possible final score.

Input Format

This problem is a submit-answer problem.

The first line of the input file contains eight integers $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$, as described in the problem statement.

The following $n$ lines, each containing $m$ integers, represent the grid $A$. Numbers are separated by a space.

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

Output Format

For the given 10 input files game1.in to game10.in, you need to submit corresponding output files game1.out to game10.out.

The first line of the output file should be an integer $M (0 \leq M \leq K)$, representing the number of operations.

The following $M$ lines should describe each operation. For each line, the first integer $l$ indicates the length of the chosen path. Next, there are $2l$ numbers, namely $x_1, y_1, x_2, y_2, \dots, x_l, y_l$.

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

1 3 100 2 3 1 1 1
2 1 1

Sample Output #2

1
2 1 2 1 3

Notes

Sample Explanation 1

The four eliminations yield numbers and scores as follows: $37$ with a score of $2+1=3$; $41$ with a score of $2+1=3$; $22$ with a score of $1+2=3$; $131$ with a score of $3+3=6$. The total score is $15$. There may be better solutions.

Sample Explanation 2

This solution involves only one elimination operation. The eliminated number is $11$, with an operation score of $2+2=4$. Since $F=1$, the final score is the sum of all operation scores $4$ divided by $2^1 = 2$ and rounded down, resulting in $2$. Choosing the path $211$ would yield the best score of $4$ for this scenario.

Scoring Criteria

For each dataset, we have set nine scoring parameters $a_{10}, a_9, \dots, a_2$. If your output is invalid, you receive zero points. Otherwise, if your game score is $w_{user}$, your score will be determined by the following table:

Additional Files

The checker needs to be compiled and used separately.

Please download the latest source code of testlib.h from Github.

见题面 Input 部分

见题面 Output 部分