题目描述

最近，小 Z 迷上了一款新型消除游戏。这款游戏在一个 $n\times m$ 的方格中进行。初始时方格中均为 $0 \sim 9$ 的整数。进行消除后方格中会出现空白，用 $-1$ 表示。为了方便，我们将第 $i$ 行，第 $j$ 列的数记为 $A_{i,j}$，并将其坐标记为 $(i,j)$。

给定三个参数 $l_{\min},l_{\max}$ 以及 $K$，玩家可以进行不超过 $K$ 次操作。对于每次操作，玩家需要在方格中找到一条长度为 $l$ 的路径。形式化地，该路径用两个长度为 $l$ 的序列 $x_1,x_2,\ldots,x_l$ 和 $y_1,y_2,\ldots,y_l$ 表示，需要满足如下条件：

1. $1\le x_i\le n,1\le y_i\le m$，其中 $1\le i\le l$，即 $(x_i,y_i)$ 对应于方格中的一个合法位置；
2. $\left|x_i-x_{i+1} \right|+ \left|y_i-y_{i+1} \right|=1$，其中 $1 \le i \lt l$，即 $(x_i,y_i)$ 与 $(x_{i+1},y_{i+1})$ 是方格中相邻的两个位置；
3. $x_i \neq x_j$ 或 $y_i \neq y_j$，其中 $1\le i \lt j\le l$，即路径不能经过重复的格子；
4. $A_{x_i,y_i} \neq -1$，其中 $1\le i\le l$，即路径不能经过空白的格子；
5. $A_{x_1,y_1} \neq 0$，即路径不能以数字 $0$ 为起点；
6. $l_{\min}\le l\le l_{\max}$，即路径的长度需要在给定的范围内。

将路径上的数字串成一个整数 $N$，形式化地

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

游戏会给出两个参数 $c_1,c_2$ 用于计算玩家本次操作的得分：

1. 如果数 $N$ 是质数，那么将获得质数得分 $l^{c_1}$，否则获得质数得分 $1$；
2. 如果数 $N$ 是回文数（即，将数 $N$ 的十进制表达看成一个字符串，这个字符串的逆序串和它本身完全相同），那么将获得回文数得分 $l^{c_2}$，否则获得回文数得分 $1$；
3. 如果质数得分和回文数得分均为 $1$，那么本次操作的得分为 $0$；否则本次操作的得分为质数得分与回文数得分之和。

每次操作过后，若该次操作的得分等于 $0$，那么你浪费了一次操作机会，而局面不会有任何改变。若该次操作的得分大于 $0$，则将路径上的数替换为空白，并使空白上方的数字垂直下落。形式化地，执行以下操作：

1. 执行 $A_{x_i,y_i}\leftarrow -1$，其中 $1\le i\le l$；
2. 枚举所有格子。如果存在某个格子 $(i ,j)$，满足 $i \neq n, A_{i,j} \neq -1, A_{i+1,j} = -1$，执行 $A_{i+1,j} \leftarrow A_{i,j}, A_{i,j}\leftarrow -1$。反复执行这个操作直到方格中不再存在这样的格子。

我们还会给你一个参数 $F$ ，在所有操作完成后，玩家的最终得分 $S$ 的计算方式由 $F$ 决定：如果 $F$ 取值为 $0$，那么玩家的最终得分为所有操作的分数总和 $m$；如果 $F$ 取值为 $1$，那么玩家的最终得分为所有操作的分数总和 $m$ 除 $2^d$ 后向下取整，即

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

其中 $d$ 为最终方格中非空白格子的数目。

小 Z 沉迷于这个有趣的游戏中不能自拔。她想请你帮助, 针对给定的输入参数，给出游戏局面的操作方案。当然，最终得分越大越好。

输入格式

本题是一道提交答案题。

对于每个输入文件，输入的第 $1$ 行包含 $8$ 个用空格分隔的整数 $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$，含义同题面描述。

随后 $n$ 行，每行 $m$ 个整数，表示方格 A。数之间用一个空格分隔。

输入文件中不会包含多余的空行，行末不会存在多余的空格。

输出格式

针对给定的 $10$ 个输入文件 game1.in ~ game10.in，你需要分别提交你的输出文件 game1.out ~ game10.out。

输出文件第 $1$ 行为一个整数 $M (0 \leq M \leq K)$，为你的操作次数。

随后, 输出文件还应包含 $M$ 行，每行描述一次操作。对于每一行，最开始的整数$l$表示这次操作中选定路径的长度。接下来有 $2l$ 个数字，分别为 $x_1, y_1, x_2, y_2, \dots, x_l, y_l$。

输出文件中不应包含多余的空格和空行。一行的多个整数之间使用一个空格分隔。

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

提示

样例解释 1

$4$ 次消除得到的数与相应的分数分别是：$37$，得分为 $2+1=3$；$41$，得分为 $2+1=3$；$22$，得分为 $1+2=3$；$131$，得分为 $3+3=6$。总共得分为 $15$。可能存在更优的方案。

样例解释 2

本方案仅一次消除操作。消除的数为 $11$，本次操作得分为 $2+2=4$。由于 $F=1$，最终得分为每次操作得分之和 $4$ 除以 $2^1 = 2$ 后下取整，为 $2$。若选择消除路径 $211$，则会得到本局面最佳分数 $4$。

评分标准

对于每组数据，我们设置了 $9$ 个评分参数 $a_{10},a_9, \dots ,a_2$。如果选手的输出不合法，则得零分。否则，在你的方案中，若游戏得分为 $w_{user}$，你的分数将会由下表给出：

得分	条件	得分	条件
$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$

附加文件

checker 需要自行编译后使用。

请前往 Github 下载 testlib.h 的最新源代码。