#214736. [POI 2025/2026 #1] 互不侵犯 / Rozwiązanie pokojowe

滥用评测者将被封号。

给定一个大小为 的国际象棋棋盘，行和列用从 1 到 的整数编号。在棋盘上放置了 个国王，用从 1 到 的整数编号。与标准国际象棋规则相同，每个国王都可以向八个方向移动，也就是说，在一步之内它可以移动到任意一个相邻的格子：即与当前所占格子共享边或顶点的格子。

国王们对当前的初始摆放不太满意，每个国王都为自己选定了一个想要到达的目标格子(可能与它的初始格子相同)。他们想通过一系列移动，把自己的位置从初始摆放变为目标摆放。每一步移动是：选择某个国王，把它从当前所在的格子移动到一个相邻的格子。整个过程中在任何时刻，都不能出现某一对国王占据相邻格子的情况。

你的任务是帮助这些国王，给出这样一系列移动，或者指出这是不可能的。

输入的第一行包含两个整数 和 （），分别表示棋盘的大小和国王的数量。接下来的 行描述初始摆放。

第 行的描述（）由 个整数组成；其中第 个数 表示：在第 行第 列的格子上，有编号为 的国王；或者如果 ，则该格子为空。

接下来的另 行以同样的方式给出目标摆放(即第 行包含 个数 ，其中 表示国王的编号，或者为 0 表示该格子为空)。

对于每个 （），都有 ，并且从 1 到 的每个整数在初始摆放 中恰好出现一次，在目标摆放 中也恰好出现一次。

在初始摆放和目标摆放中，任意两个国王都不占据相邻的格子。

你的程序应在第一行输出单词 TAK，如果存在所需的移动序列；否则输出单词 NIE。

如果答案是 TAK，则第二行应输出一个整数 （），表示你的方案中的移动步数。可以证明，如果所需的移动序列存在，那么存在一个满足上述长度限制的序列。

在接下来的 行中，你需要输出依次进行的每一步移动的描述。

每一行应包含三个整数 ，表示编号为 的国王应移动到第 行第 列的格子上。该格子必须与该国王当前所在格子相邻（特别地，不能是它当前所在的格子本身），并且不能与任何其他国王所占据的格子相邻。

样例输入 1

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

样例输出 1

TAK
13
3 3 1
2 2 3
3 4 2
3 4 3
3 4 4
2 3 2
1 1 2
1 1 3
2 3 1
3 3 3
3 4 4
2 4 2
1 2 3

样例输入 2

5 8
1 0 2 0 3
0 0 0 0 0
4 0 5 0 6
0 0 0 0 0
7 0 8 0 0
2 0 3 0 0
0 0 0 0 6
4 0 1 0 0
0 0 0 0 8
7 0 5 0 0

样例输出 2

NIE

大样例

可以在附件中获得大样例。

样例 和 是题面中展示的样例。此外

• ：
  • ；
  • 如果 且 为奇数，否则 ；
  • 如果 且 为奇数，否则 。

子任务

本题采用捆绑测试。

对于每个子任务，在该子任务中价值一半分数的测试里 为奇数，在价值另一半分数的测试里 为偶数。

在洛谷上评测时，我们将子任务 （）设置为子任务 中 为偶数的测试点；子任务 类似。

如果你的答案只有第一行是正确的，你的解在该测试上将获得 的分数。为了得到这部分分数，你不必输出后续各行。