我们有一个大小为 $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}$ 的国王（当 $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^6$），表示你方案中的移动步数。可以证明，如果存在满足要求的序列，则必然存在一个满足上述长度限制的序列。

在接下来的 $m$ 行中，应输出每一步移动的描述。每行应包含三个整数 $c, i, j$，表示国王 $c$ 应该移动到第 $i$ 行第 $j$ 列的格子。该目标格子必须与该国王当前占用的格子相邻（特别地，不能是同一个格子），且不能与任何其他国王当前占用的格子相邻。

样例

输入样例 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

说明

样例测试：测试 0a 和 0b 是上面的两个样例。此外：

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

子任务

测试点被划分为以下子任务。每个子任务的测试由两组或更多独立的测试组组成。对于每个子任务，在占一半分数的测试中 $n$ 为奇数，在占另一半分数的测试中 $n$ 为偶数。

如果你的输出中只有第一行（TAK/NIE）正确，你的程序将获得该测试点 20% 的分数。你不需要输出后续的行即可获得这些分数。