最近，小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\le x_i\le n$, $1\le y_i\le m$，其中$1\le i\le l$，即$(x_i,y_i)$对应于方格中的一个合法位置；
- $\left|x_i-x_{i+1} \right|+ \left|y_i-y_{i+1} \right|=1$，其中$1 \le i < l$，即$(x_i,y_i)$与$(x_{i+1},y_{i+1})$是方格中相邻的两个位置；
- $x_i \neq x_j$ 或 $y_i \neq y_j$，其中 $1\le i < j\le l$，即路径不能经过重复的格子；
- $A_{x_i,y_i} \neq -1$，其中$1\le i\le l$，即路径不能经过空白的格子；
- $A_{x_1,y_1} \neq 0$，即路径不能以数字$0$为起点；
- $l_{min}\le l\le l_{max}$，即路径的长度需要在给定的范围内。
将路径上的数字串成一个整数$N$，形式化地
\begin{equation} N=\sum\limits_{i=1}^l A_{x_i,y_i}\times 10^{l-i} \end{equation}
游戏会给出两个参数$c_1$, $c_2$用于计算玩家本次操作的得分：
- 如果数$N$是质数，那么将获得质数得分$l^{c_1}$，否则获得质数得分$1$。
- 如果数$N$是回文数（即，将数$N$的十进制表达看成一个字符串，这个字符串的逆序串和它本身完全相同），那么将获得回文数得分$l^{c_2}$，否则获得回文数得分$1$。
- 如果质数得分和回文数得分均为$1$，那么本次操作的得分为$0$；否则本次操作的得分为质数得分与回文数得分之和。
每次操作过后，若该次操作的得分等于$0$，那么你浪费了一次操作机会，而局面不会有任何改变。若该次操作的得分大于$0$，则将路径上的数替换为空白，并使空白上方的数字垂直下落。形式化地，执行以下操作：
- 执行$A_{x_i,y_i}\leftarrow -1$，其中$1\le i\le l$。
- 枚举所有格子。如果存在某个格子$(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$ ，在所有操作完成后，玩家的最终得分的计算方式由$F$决定：如果$F$取值为$0$，那么玩家的最终得分为所有操作的分数总和；如果$F$取值为$1$，那么玩家的最终得分为所有操作的分数总和除$2^d$后向下取整，即 \begin{equation} \text{最终得分} = \begin{cases} \text{所有操作的分数之和}, & F=0\\\\ \left \lfloor \frac{\text{所有操作的分数之和}}{2^d} \right \rfloor, & F=1 \end{cases} \end{equation}
其中$d$为最终方格中非空白格子的数目。
小Z沉迷于这个有趣的游戏中不能自拔。她想请你帮助, 针对给定的输入参数，给出游戏局面的操作方案。当然，最终得分越大越好。
输入格式
所有输入数据game1.in ~ game10.in见数据下载。 输入的第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$。
输出文件中不应包含多余的空格和空行。一行的多个整数之间使用一个空格分隔。
样例一
input
3 3 100 2 3 1 1 0 2 1 1 2 3 3 4 7 1
output
4 2 2 2 3 2 2 3 1 3 2 2 2 1 3 1 3 1 3 2 3 3 3
explanation
4次消除得到的数与相应的分数分别是：37，得分为2+1=3；41，得分为2+1=3；22，得分为1+2=3；131，得分为3+3=6。总共得分为15。可能存在更优的方案。
样例二
input
1 3 100 2 3 1 1 1 2 1 1
output
1 2 1 2 1 3
explanation
本方案仅一次消除操作。消除的数为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} \geq a_{10}$ | 5 | $w_{user} \geq a_5$ |
| 9 | $w_{user} \geq a_9$ | 4 | $w_{user} \geq a_4$ |
| 8 | $w_{user} \geq a_8$ | 3 | $w_{user} \geq a_3$ |
| 7 | $w_{user} \geq a_7$ | 2 | $w_{user} \geq a_2$ |
| 6 | $w_{user} \geq a_6$ | 1 | $w_{user} > 0$ |
如何测试你的输出
在终端中先切换到该试题的目录下：（windows用户请使用cmd）
cd game
我们提供checker这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是，在终端中运行
./checker_linux64 <case_no>
其中case_no是测试数据的编号。例如
./checker_linux64 3
将测试game3.out是否可以接受。（windows用户请使用checker_win32 3）（什么你是windows 64位？放心吧可以运行win32应用程序的。）
当然我们有对应的linux 32位版本：checker_linux32。如果linux用户发现无法运行程序，请尝试执行chmod +x checker_linux64或chmod +x checker_linux32后重试。
其它操作系统请安装 node.js 然后使用 node checker.js <case_no> 运行checker。
在你调用这个程序后，checker将根据你给出的输出文件给出测试的结果。
鄂公网安备 42010202000505 号