Recently, Little Z has become obsessed with a new type of elimination game. This game is played on an $n \times m$ grid. Initially, the grid contains integers from $0$ to $9$. After an elimination, the grid will contain empty spaces, represented by $-1$. For convenience, 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 at most $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, \dots, x_l$ and $y_1, y_2, \dots, y_l$, which must satisfy the following conditions:
- $1 \le x_i \le n, 1 \le y_i \le m$, where $1 \le i \le l$, meaning $(x_i, y_i)$ corresponds to a valid position in the grid;
- $|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$, where $1 \le i < l$, meaning $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ are adjacent positions in the grid;
- $x_i \neq x_j$ or $y_i \neq y_j$, where $1 \le i < j \le l$, meaning the path cannot pass through the same cell twice;
- $A_{x_i, y_i} \neq -1$, where $1 \le i \le l$, meaning the path cannot pass through empty cells;
- $A_{x_1, y_1} \neq 0$, meaning the path cannot start with the digit $0$;
- $l_{\min} \le l \le l_{\max}$, meaning the length of the path must be within the given range.
The digits on the path are concatenated to form an integer $N$, formally: $$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 the current operation: 1. If $N$ is a prime number, you receive the prime score $c_1^1$, otherwise you receive the prime score $1$. 2. If $N$ is a palindrome (i.e., the decimal representation of $N$ read as a string is identical to its reverse), you receive the palindrome score $c_2^1$, otherwise you receive the palindrome score $1$. 3. If both the prime score and the palindrome score are $1$, the score for this operation is $0$; otherwise, the score for this operation is the sum of the prime score and the palindrome score.
After each operation, if the score for that operation is $0$, you have wasted an operation opportunity, and the state of the grid remains unchanged. If the score for that operation is greater than $0$, the numbers on the path are replaced with empty spaces, and the numbers above the empty spaces fall vertically. Formally, perform the following operations: 1. Execute $A_{x_i, y_i} \leftarrow -1$, where $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$, execute $A_{i+1, j} \leftarrow A_{i,j}, A_{i,j} \leftarrow -1$. Repeat this operation until no such cells exist in the grid.
We will also provide you with a parameter $F$. After all operations are completed, the player's final score is determined by $F$: if $F$ is $0$, the player's final score is the sum of the scores of all operations; if $F$ is $1$, the player's final score is the sum of the scores of all operations divided by $2^d$ and rounded down, i.e., $$\text{Final Score} = \begin{cases} \text{Sum of all operation scores}, & F = 0 \\ \lfloor \frac{\text{Sum of all operation scores}}{2^d} \rfloor, & F = 1 \end{cases}$$ where $d$ is the number of non-empty cells in the final grid.
Little Z is addicted to this interesting game. She wants your help to provide an operation plan for the given input parameters. Of course, the higher the final score, the better.
Input
The first line contains 8 space-separated integers $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$, with meanings as described in the problem statement. Following are $n$ lines, each containing $m$ integers, representing the grid $A$. Numbers are separated by a single space. The input file does not contain extra empty lines, and there are no extra spaces at the end of lines.
Output
For each of the 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 \le M \le K$), representing your number of operations.
Subsequently, the output file should contain $M$ lines, each describing one operation. For each line, the first integer $l$ represents the length of the path selected in this operation. Next are $2l$ numbers, which are $x_1, y_1, x_2, y_2, \dots, x_l, y_l$.
The output file should not contain extra spaces or empty lines. Multiple integers on a line are separated by a single space.
The output file size cannot exceed 1 MB. It is guaranteed that a valid output file size will not exceed this limit.
Examples
Input 1
3 3 100 2 3 1 1 0 2 1 1 2 3 3 4 7 1
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
Note 1
4次消除得到的数与相应的分数分别是：37，得分为 2 + 1 = 3；41，得分为 2 + 1 = 3；22，得分为 1 + 2 = 3；131，得分为 3 + 3 = 6。总共得分为 15。可能存在更优的方案。
Input 2
1 3 100 2 3 1 1 1 2 1 1
Output 2
1 2 1 2 1 3
Note 2
本方案仅一次消除操作。消除的数为 11，本次操作得分为 2 + 2 = 4 。由于 F = 1，最终得分为每次操作得分之和 4 除以 2^1 = 2 后下取整，为 2 。若选择消除路径 211 ，则会得到本局面最佳分数 4 。
Scoring
For each set of data, we have set 9 scoring parameters $a_{10}, a_9, a_8, \dots, a_2$. If the contestant's output is invalid, they receive zero points. Otherwise, in your plan, if the game score is $w_{\text{user}}$, your score will be given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $w_{\text{user}} \ge a_{10}$ | 5 | $w_{\text{user}} \ge a_5$ |
| 9 | $w_{\text{user}} \ge a_9$ | 4 | $w_{\text{user}} \ge a_4$ |
| 8 | $w_{\text{user}} \ge a_8$ | 3 | $w_{\text{user}} \ge a_3$ |
| 7 | $w_{\text{user}} \ge a_7$ | 2 | $w_{\text{user}} \ge a_2$ |
| 6 | $w_{\text{user}} \ge a_6$ | 1 | $w_{\text{user}} > 0$ |