Problem Description

You must have played the 8-puzzle game. It is played on a $3 \times 3$ grid, where $1$ blank cell and the $8$ numbers from $1 \sim 8$ are distributed in the $3 \times 3$ grid with no repetition and no omission.

For example:

5 2 8
1 3 _
4 6 7

During the game, you can swap the blank cell with the number in one of the four directions: up, down, left, or right (if such a cell exists).

For example, in the case above, the blank can be swapped with the numbers to its left, above, or below, resulting in:

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

The odd sliding puzzle is an extension of it. It is played on an $n \times n$ grid, where $n$ is odd. One blank cell and the $n^2 - 1$ numbers from $1 \sim n^2-1$ are distributed in the $n \times n$ grid with no repetition and no omission.

The rule for moving the blank is the same as in the 8-puzzle game. In fact, the 8-puzzle is exactly the odd sliding puzzle with $n=3$.

Now, given two configurations of an odd sliding puzzle, determine whether there exists a sequence of blank moves that can transform one configuration into the other.

Input Format

Multiple test cases. For each test case:

The first line contains an integer $n$, where $n$ is odd.

The next $n$ lines contain $n$ integers each, describing the first configuration.

The next $n$ lines contain $n$ integers each, describing the second configuration.

Each integer in a configuration is one of $0 \sim n^2-1$. Here, $0$ represents the blank cell, and the other values have the same meaning as in the odd sliding puzzle. It is guaranteed that these integers appear with no repetition and no omission.

Output Format

For each test case, if the two configurations are reachable from each other, output TAK. Otherwise, output NIE.

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

TAK
TAK

Hint

Constraints: $1 \le n < 500$.

Translated by ChatGPT 5