问题描述

有 $N$ 行 $N$ 列共 $N × N$ 个正方形的面板。你将使用这些面板进行游戏。

游戏的目标是尽量使所有面板的颜色都相同。初始时，每个面板都被涂上了从颜色 $1$ 到颜色 $K$ 的 $K$ 种颜色之一。

通过触摸一个面板，并将其变成任意颜色，你可以改变该面板的颜色。设触摸的面板颜色为 $i$，想要变成的颜色为 $j$。那么，从触摸的面板出发，只有上下左右相邻的颜色为 $i$ 的面板才会变成颜色 $j$。

这个游戏的最终得分可以通过以下计算公式得到：

• 假设出现次数最多的颜色为 $i$，每当颜色为 $i$ 的面板出现一次，得 $100$ 分。
• 每触摸一次面板，失去 $1$ 分。
• 但是，如果总共触摸面板超过 $10000$ 次，系统会崩溃，得 $0$ 分。

给定面板的初始状态。输出触摸操作步骤，以获得尽可能高的得分。

注意，本问题中的输入是完全公开的，每个输入都有独立的通行证号id。你可以利用这一点来解决问题。

此外，C++判分器也已经公开。你也可以使用它进行验证。

约束条件

• $1$ ≤ id ≤ $50$
• $N$ = $100$
• $K$ = $9$
• $S_i$ 是一个长度为 $N$ 的字符串，第 $j$ 个字符 $S_{i,j}$ 是 1~K 中的一个数字，表示第 $i$ 行、第 $j$ 列（记为 $(i,j)$）的面板颜色为 $S_{i,j}$。
• $S$ 中的字符选取概率相等且独立随机，范围是 1~K。
• 输入与此链接提供的zip文件相同。

输入

id $N$ $K$ $S_1$ $S_2$ : $S_N$

输出

按照以下格式输出结果。其中，$Q$ 是触摸面板的次数，$Y_i, X_i, C_i$ 分别表示第 $i$ 次触摸的面板的行索引 $Y_i$、列索引 $X_i$（记为 $(Y_i, X_i)$），以及要变成的颜色为 $C_i$。

$Q$ $Y_1$ $X_1$ $C_1$ $Y_2$ $X_2$ $C_2$ : $Y_Q$ $X_Q$ $C_Q$

你的分数将是对50个测试用例的得分之和。

输入示例 1

0 6 9
515795
153859
833597
333419
333121
533917

输出示例 1

2
5 5 1
5 2 1

这个示例输入是为了说明目的而使用的较小的输入。

面板的初始状态如下：

然后按照输出中的步骤，触摸两次面板。

首先，将 $(5,5)$ 的面板颜色变为颜色 $1$。此时，在相邻面板中，只有原来颜色为 $2$ 的面板不存在，因此只有该面板的颜色发生改变。

接下来，将 $(5,2)$ 的面板颜色改为颜色 $1$。此时，只要通过上下左右相邻的颜色为 $3$ 的面板，就可以达到所有面板变成颜色 $1$ 的目标，所以面板的颜色会发生以下改变。

在操纵了所有面板后，颜色出现最多的面板是颜色 $1$，共有 $18$ 个。

因此，得分为 $18 × 100 - 2 = 1798$。