We are given an $n \times n$ chessboard, where rows and columns are numbered with integers from $1$ to $n$. There are $k$ kings placed on the board, numbered with integers from $1$ to $k$. As in a standard game of chess, each king can move in eight directions, meaning in one move it can move to any adjacent square: one that shares a side or a corner with the currently occupied square.

The kings are not entirely satisfied with their initial configuration, and each has chosen a target square where it would like to be (possibly the same as its initial square). They want to change their initial configuration to the target one by performing a sequence of moves. Each move consists of a king moving from its currently occupied square to an adjacent square. At no point during this process can any pair of kings occupy adjacent squares.

Your task is to help the kings and provide such a sequence of moves or determine that it is impossible.

Input

The first line of input contains two integers $n$ and $k$ ($1 \le n \le 100$, $1 \le k \le 2\,500$) representing the size of the board and the number of kings. The next $n$ lines contain the description of the initial configuration. The description of the $i$-th row (for $1 \le i \le n$) consists of $n$ numbers; the $j$-th of these numbers $a_{i,j}$ indicates that a king with number $a_{i,j}$ is located at the square in row $i$ and column $j$ if $a_{i,j} > 0$, or that the square is empty if $a_{i,j} = 0$. The following $n$ lines contain the description of the target configuration provided in the same way (i.e., the $i$-th row contains $n$ numbers $b_{i,j}$, where $b_{i,j}$ denotes the king number or $0$ if the square is empty). For every $i, j$ ($1 \le i, j \le n$), $0 \le a_{i,j}, b_{i,j} \le k$ holds, and each number from $1$ to $k$ appears exactly once in the initial configuration $a$ and exactly once in the target configuration $b$. In both the initial and target configurations, no two kings occupy adjacent squares.

Output

Your program should output the word TAK in the first line if a sequence of moves exists, or NIE otherwise. If the answer is TAK, the second line should contain the number $m$ ($0 \le m \le 5 \cdot 10^6$) representing the number of moves in your solution. It can be proven that if such a sequence exists, there exists a sequence satisfying this length constraint. The next $m$ lines should contain descriptions of the consecutive moves. Each line should consist of three numbers $c, i, j$ meaning that king $c$ should move to the square in row $i$ and column $j$. This must be a square adjacent to the square currently occupied by that king (in particular, it cannot be the same square), which is not adjacent to the square occupied by any other king.

Examples

Input 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

Output 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

Input 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

Output 2

NIE

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of two or more separate groups of tests. For each subtask, in tests worth half the points, $n$ is odd, and in tests worth the other half, $n$ is even.

If only the first line of your answer is correct, your solution will receive 20% of the points for that test. You do not need to output the subsequent lines to receive these points.