Relative Order

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenik has two integer arrays \(a_i\) and \(b_i\). All \(2n\) values of the arrays are distinct.

Zenik wants to form a single permutation array of \(n\) elements. To do this, he first chooses a string of \(n\) characters, where each character is either 1 or 2. Then he creates an intermediate array of \(n\) elements, in which the \(i\)-th position contains \(a_i\) if the \(i\)-th character of the string is 1, and \(b_i\) if it is 2. Next, he writes down an array in which the first place is the index of the minimum in the intermediate array, the second place is the index of the 2nd smallest value, and the \(i\)-th place is the index of the \(i\)-th smallest value.

For example, let array \(a\) be [3, 1, 7, 4], array \(b\) be [47, 2, 10, 8], and the string be 2122. Then the intermediate array is [47, 1, 10, 8]. The minimum value in this array is at position 2, the 2nd smallest value at position 4, the 3rd at position 3, and the 4th at position 1. Therefore, the result is [2, 4, 3, 1].

Marichka is curious whether there exist 2 different strings of characters 1 and 2 such that the permutations obtained in this way are identical.

Input

The first line contains a single integer \(n\).

The second line contains \(n\) integers \(a_i\).

The third line contains \(n\) integers \(b_i\).

Output

In the first line, output TAK if 2 different strings exist that form the same permutation, and NI if no such strings exist.

If the strings exist, in the next two lines output them. Each string must be of length \(n\) consisting of characters 1 and 2, and the strings must be different.

If there are many different pairs of strings, output any pair.

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(0 \le a_i, b_i \le 10^9\),

All values \(a_i\) and \(b_i\) are distinct.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 1 7 4 47 2 10 8	TAK 2122 2211