The Great Annual Robot Tournament is taking place in Byteotia, featuring $n$ robots numbered from $1$ to $n$. The $i$-th robot is described by two parameters, $s_i$ and $z_i$ ($1 \le s_i, z_i \le n$), which represent its strength and agility, respectively. The values $s_i$ are pairwise distinct, and the values $z_i$ are also pairwise distinct.

The tournament consists of a series of duels. Each duel involves two robots that have not yet been eliminated. In a duel between the $i$-th robot and the $j$-th robot, the first robot eliminates the second if it is stronger or more agile, i.e., if $s_i > s_j$ or $z_i > z_j$. Similarly, the second robot eliminates the first if $s_i < s_j$ or $z_i < z_j$. Note that this means it is possible for both robots to be eliminated in the same duel. If a robot is not eliminated in a duel, it may participate in subsequent ones.

The tournament broadcast is most popular when all robots are eventually eliminated. Your task is to determine whether it is possible to choose a sequence of duels such that this happens.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 200\,000$). The next $n$ lines contain the descriptions of the robots. The description of the $i$-th robot (for $1 \le i \le n$) consists of two integers $s_i, z_i$ ($1 \le s_i, z_i \le n$). You may assume that the numbers $s_1, s_2, \dots, s_n$ are pairwise distinct. You may also assume that the numbers $z_1, z_2, \dots, z_n$ are pairwise distinct.

Output

In the first and only line of output, print the word TAK if it is possible to choose a sequence of duels such that all robots are eventually eliminated. Otherwise, print the word NIE.

Examples

Input 1

4
1 4
2 2
3 3
4 1

Output 1

TAK

Note 1

We have $s_1 = 1, z_1 = 4, s_2 = 2, z_2 = 2, s_3 = 3, z_3 = 3, s_4 = 4, z_4 = 1$. If, for example, the first two robots participate in the first duel, and the next two robots participate in the second duel, all robots will be eliminated.

Input 2

2
1 1
2 2

Output 2

NIE

Sample tests

Tests 0a and 0b are the tests from the examples above. Additionally:

• 1ocen: $n = 8$, $s_i = i$ and $z_i = n - i + 1$ for each $1 \le i \le n$. Answer: TAK.
• 2ocen: $n = 20$ and there exists a robot that can defeat every other robot, and no robot can defeat it. Answer: NIE.
• 3ocen: $n = 500$ and all robots can be paired up such that the robots in each pair eliminate each other. Answer: TAK.
• 4ocen: $n = 200\,000$, $s_i = i$ and $z_i = i$ for $1 \le i \le \frac{n}{2}$, and $s_i = i$ and $z_i = \frac{3n}{2} - i + 1$ for $\frac{n}{2} < i \le n$. Answer: TAK.
• 5ocen: $n = 5$, a small correctness test. Answer: TAK.

Evaluation

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