题目背景

滥用评测者将被封号。

题目描述

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

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

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

输入格式

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

第 $i$ 行的描述（$1 \le i \le n$）由 $n$ 个整数组成；其中第 $j$ 个数 $a_{i,j}$ 表示：在第 $i$ 行第 $j$ 列的格子上，有编号为 $a_{i,j} > 0$ 的国王；或者如果 $a_{i,j} = 0$，则该格子为空。

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

对于每个 $i, j$（$1 \le i, j \le n$），都有 $0 \le a_{i,j}, b_{i,j} \le k$，并且从 1 到 $k$ 的每个整数在初始摆放 $a$ 中恰好出现一次，在目标摆放 $b$ 中也恰好出现一次。

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

输出格式

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

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

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

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

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

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

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
0 0 0 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

NIE

提示

大样例

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

样例 $\texttt{0a}$ 和 $\texttt{0b}$ 是题面中展示的样例。此外

• $\texttt{0c}$：
  • $n = 100, k = 50$；
  • $a_{i,j} = (i+1)/2$ 如果 $i=j$ 且 $i$ 为奇数，否则 $a_{i,j} = 0$；
  • $b_{i,j} = 51 - (i+1)/2$ 如果 $i=j$ 且 $i$ 为奇数，否则 $b_{i,j} = 0$。

子任务

本题采用捆绑测试。

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

在洛谷上评测时，我们将子任务 $2i$（$1\le i\le 4$）设置为子任务 $i$ 中 $n$ 为偶数的测试点；子任务 $(2i-1)$ 类似。

子任务编号	限制	得分
$1$	$n \le 5$	$18$
$2$	$2k \le n$	$16$
$3$	$n \le 40$	$38$
$4$	无额外限制	$28$

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