Bajtazar gave his son, Bajtek, a deck of cards as a gift. The deck consists of $n$ cards, numbered from 1 to $n$.

Bajtek was very happy with the gift. He spent the whole evening in his room playing with the cards, shuffling them. He became so skilled that every time he shuffled, the result was the same: the card at position $k$ (for $1 \le k \le n$) always moved to position $a_k$ (where $1 \le a_k \le n$).

At some point, Bajtazar came into Bajtek's room and said it was time to sleep. Bajtek begged his father to show him how to shuffle cards before going to bed. Bajtazar then shuffled the cards such that the card at position $k$ moved to position $b_k$ (where $1 \le k, b_k \le n$).

Bajtek watched with admiration at how skillfully his father shuffled the cards. He wanted to be able to do the same! Unfortunately, Bajtek is still small and cannot shuffle like his father. However, he came up with the idea of trying to repeat his own shuffling method several times to eventually achieve the same arrangement as his father's shuffle.

Now the boy cannot sleep because he is wondering if this is even possible. Help him!

Input

The first line of input contains a single integer $n$ ($2 \le n \le 1\,000\,000$). The second and third lines contain the descriptions of the permutations $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$, which are sequences of $n$ distinct integers from 1 to $n$. You may assume that these two permutations are different.

Output

The first and only line of output should contain one word, TAK or NIE, depending on whether there exists an integer $k > 1$ such that repeating Bajtek's shuffle $k$ times results in the same arrangement as Bajtazar's shuffle.

Examples

Input 1

4
2 4 3 1
1 2 3 4

Output 1

TAK

Input 2

4
1 2 3 4
2 4 3 1

Output 2

NIE