本题为提交答案题，请注意比赛中途提交上去后，对于每个测试点如果有分就会显示该测试点满分，比赛完后会进行重测给出真实的分数，请特别注意！

九条可怜是一个可爱的男孩子。

九条可怜在一家果冻生产厂家工作。这个果冻厂专门生产 $1\text{米} \times 1\text{米} \times 1\text{米}$ 的巨型果冻，在果冻生产出来以后，他们会把果冻装到一个 $1\text{米} \times n\text{米} \times m\text{米}$ 大小的集装箱中用卡车运走。

这个果冻厂生产的果冻有一个特点：一旦两个同类型果冻的一个面贴合在了一起，那么静置几秒之后这两个果冻就会粘在一起无法拉开。不同类型的果冻由于切面纹理不同所以并不会粘连。

由于果冻数量多起来之后切合面是平方级别增长的，到时候切开就会特别麻烦。所以在集装箱中还有一些用来将果冻隔开的块状物，每个块状物是由大小为 $1\text{米} \times 1\text{米} \times 1\text{米}$ 的立方体拼起来得到的。

块状物也分为已经固定的和尚未固定的两种，已经固定的表示这个块已经和两边的墙壁相连无法移动，而尚未固定的则可以和果冻一样被推动和掉落。

由于某些切面可能已经老化，所以初始状态下一个果冻可能和墙壁或者另一个块状物粘连。

九条可怜的工作是检查将要出发的卡车，使得卡车内部装货的位置尽量稳定，假如果冻过于分散，那么运输过程中的颠簸可能会影响品质。

最近，果冻厂新招了一批临时工，所以果冻的摆放非常杂乱，九条可怜需要尽量减少果冻形成的连通块的个数来保持稳定（由于果冻和墙壁之间的连接不够稳定，连通块只计算相同颜色的果冻之间相连的边）。显然，能够达成的最少连通块个数一定等于颜色数。

为了帮助九条可怜解决这个问题，公司为九条可怜分配了一个得力助手：海灵吨。

每次，海灵吨可以选择一个连通块，将它向左或向右推 $1$ 米。在推的过程中，所有“挡路的”连通块也会被向同一个方向推 $1$ 米。

当然，由于海灵吨并没有办法推动一个固定方块（包括和一个固定方块连通的方块），假如某一个操作中需要推动一个固定方块，那么这一个操作就是不合法的。

在这些方块都移动了 $1$ 米之后，所有的方块会开始掉落。所有掉落完成之后就会进入静置时间，任何相邻的相同类型的果冻在这时就会被粘连形成一个大的连通块。

为了让海灵吨节省体力，九条可怜想知道，将这些块合并成最小块数的情况下最少需要多少次操作。

输入格式

所有输入数据 C1.in~C20.in 见数据下载。 输入的第一行包含两个正整数 $n, m$，含义同题面描述。

随后 $2n-1$ 行，每行 $2m-1$ 个字符，表示初始状态。对于第 $x$ 行第 $y$ 个字符：

1. 假如 $x$ 是奇数且 $y$ 是奇数：这个格子代表一个方块，0 代表已经固定的块状物，9 代表尚未固定的块状物，1 到 8 代表不同颜色的果冻，. 代表这个格子是空的。
2. 假如 $x$ 是偶数且 $y$ 是偶数：这个格子是一个空格。
3. 否则，字符为 | 或 -，表示相邻的两个格子之间是否被粘连。

下一行包含两个空格分隔的整数 $a_1,a_2$，用途将在后面提到。

输出格式

针对给定的 20 个输入文件 C1.in～C20.in，你需要分别提交你的输出文件 C1.out～C20.out。

输出文件每行使用三个数 $x,y,z$ 表示一个操作，其中 $x,y$ 表示需要移动的位置的坐标（即从左下角开始向右移动 $x-1$ 步后向上移动 $y-1$ 步到达的位置），$z$ 表示推动的方向（$0$ 表示向左，$1$表 示向右）。

样例

input

4 7
0 1 2-2 . 1-0
|           |
0-0-0 . . 0-0
|           |
0 . . 9-9 2 0
|           |
0-0-0-0-0-0-0
0 0

output

6 2 0
2 4 1
3 4 1
4 4 1

评分方式

对于每组数据，我们设置了 $2$ 个评分参数 $a_1,a_2$，并且已经在输入文件中给出。

对于每个测试点，若你有一步的输出不合法，或者你最终状态下的 $\text{块数} > \text{颜色数}+1$ 得 $0$ 分，否则设你使用的操作数为 $x$，我们给出的参考解为$y$，那么：

1. 如果 $\text{块数} = \text{颜色数}+1$，得 $1$ 分；
2. 否则，如果 $x \leq y$，得 $5$ 分；
3. 否则，如果 $x \leq y+a_1$，得 $4$ 分；
4. 否则，如果 $x \leq y+a_2$，得 $3$ 分；
5. 否则，得$2$分。

如何测试你的输出

本题有附加文件 checker.cpp，是一个本地的校验器的 C++ 代码，请选手自行编译使用。

本地校验器没有严格检查格式，请及时提交OJ以防意外爆零

将checker.cpp编译成checker后，在终端中运行

./checker <case_no>

其中case_no是测试数据的编号。例如

./checker 3

将测试C3.out是否可以接受同时在report.out里输出详细内容（windows用户请使用checker 3）。

直接在终端中运行./checker将测试所有数据是否可以接受。

运行./checker <input> <output>将测试以<input>作为输入<output>作为输出是否可以接受。

下载

输入数据及checker下载