题目重排

最近，小 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. $|x_i - x_{i+1}| + |y_i - y_{i+1}| = 1$（$1 \le i < l$），即路径相邻位置在方格中相邻；
3. $x_i \neq x_j$ 或 $y_i \neq y_j$（$1 \le i < 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_{i=1}^l A_{x_i,y_i} \times 10^{l-i}$$

游戏给出两个参数 $c_1,c_2$ 计算本次操作得分：

• 若 $N$ 是质数，质数得分为 $l^{c_1}$，否则为 $1$；
• 若 $N$ 是回文数（十进制字符串逆序与原串相同），回文数得分为 $l^{c_2}$，否则为 $1$；
• 若两者均为 $1$，本次操作得分为 $0$；否则得分为两者之和。

每次操作后，若得分大于 $0$，则将路径上的数替换为空白（$A_{x_i,y_i} \leftarrow -1$），并使空白上方的数字垂直下落：枚举所有格子，若存在 $(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$，反复执行直到无此类格子。若得分等于 $0$，则浪费一次操作机会，局面不变。

另有参数 $F$ 决定最终得分 $S$ 的计算方式：

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

其中 $m_{\text{总}}$ 为所有操作的分数总和，$d$ 为所有操作完成后方格中非空白格子的数目。

小 Z 希望得到尽可能大的最终得分，需针对给定输入参数给出操作方案。

输入格式

所有输入数据为 game1.in ~ game10.in。输入第 1 行包含 8 个整数 $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$，含义同题面。 随后 $n$ 行，每行 $m$ 个整数，表示方格 $A$，数之间用空格分隔。 输入文件无多余空行，行末无多余空格。

输出格式

针对每个输入文件，输出对应 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$。 输出文件无多余空格和空行，一行中多个整数用空格分隔。

样例 1

输入：

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

说明：4 次消除得到的数与分数分别为 37（3 分）、41（3 分）、22（3 分）、131（6 分），总得分 15，可能存在更优方案。

样例 2

输入：

1 3 100 2 3 1 1 1
2 1 1

输出：

1
2 1 2 1 3

说明：消除的数为 11，本次得分为 4。因 $F=1$，最终得分 $\lfloor 4 / 2^1 \rfloor = 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} < a_6$
9	$a_9 \le w_{user} < a_{10}$	4	$a_4 \le w_{user} < a_5$
8	$a_8 \le w_{user} < a_9$	3	$a_3 \le w_{user} < a_4$
7	$a_7 \le w_{user} < a_8$	2	$a_2 \le w_{user} < a_3$
6	$a_6 \le w_{user} < a_7$	1	$0 < w_{user} < a_2$

测试方法

附加文件提供 checker.cpp，编译命令：

g++ checker.cpp -o checker -O2

测试命令（Linux）：

./checker <case_no>

测试命令（Windows）：

checker <case_no>

其中 <case_no> 为测试点编号，需将 game*.in/out 与 checker 置于同一目录。