After many years of cold diplomatic relations between Bytocja and Bitocja, both countries have decided to warm them up by establishing closer relations between the cities of both countries.

There are $n$ cities in Bytocja and $n$ cities in Bitocja. The governments want to establish partner cities between them, i.e., assign exactly one partner city from Bitocja to each city in Bytocja and vice versa: exactly one partner city from Bytocja to each city in Bytocja.

Messages will be frequently exchanged between partner cities, so it is important that the postal codes of these cities are appropriate. Each city in Bytocja has a unique postal code, which is an integer. The same applies to Bitocja, but it may happen that a certain city in Bytocja and a certain city in Bitocja have the same postal code. Public opinion experts predict that if a city in Bytocja with postal code $a_i$ establishes a partnership with a city in Bitocja with postal code $b_j$, the venture will increase the happiness of the residents of these cities by $a_i \oplus b_j$. Here, $\oplus$ denotes the exclusive OR (XOR) operation: the $i$-th bit of the result of $x \oplus y$ is equal to 1 if and only if exactly one of the $i$-th bits of the numbers $x$ and $y$ is equal to 1.

The governments are now wondering how to pair the cities. This is not easy, because for every chosen pair, at least one city in the pair must be satisfied, i.e., no other choice of partner city for this city can increase the happiness in that city more.

Write a program that checks whether it is possible to establish partner cities that meet the residents' requirements, and if so, finds any such pairing.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 50\,000$) representing the number of cities in each country.

The second line contains a sequence of $n$ distinct integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$) representing the postal codes of the consecutive cities in Bytocja. The third line contains a sequence of $n$ distinct integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^{18}$) representing the postal codes of the consecutive cities in Bitocja.

Output

If it is not possible to assign partner cities such that for every pair at least one city is satisfied, output the single word NIE.

Otherwise, in the first line of output, print the single word TAK. Then, in the next line, print $n$ integers: the $i$-th of which is $m_i$, meaning that the city in Bytocja with index $i$ is to establish a partnership with the city in Bitocja with index $m_i$.

If there is more than one correct answer, your program may output any of them.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

You can receive 50% of the points for a given test if only the first line of the output is correct. Remember that your program must still fit within the memory and time limits.

Examples

Input 1

3
2 5 4
3 5 1

Output 1

TAK
2 1 3

Input 2

3
2 5 1
3 5 1

Output 2

NIE

Input 3

2
1 1123438534808147
0 2462061299839

Output 3

TAK
2 1