Domino Chain

Limits: 2 sec., 512 MiB

Marichka gave Zenyk a sequence of \(n\) dominoes. Each domino consists of two halves, and each half has some number of dots on it.

Zenyk wants to lay all the dominoes out in a row in the given order. Any domino may be flipped, which swaps its left and right halves. The dominoes may not be reordered.

The row is laid out correctly if, for every two adjacent dominoes, the number of dots on the right half of the first one equals the number of dots on the left half of the second one. Help Zenyk find out whether the given sequence can be laid out correctly.

Input

The first line contains one integer \(n\) – the number of dominoes.

Each of the next \(n\) lines contains two integers \(a_i\) and \(b_i\) – the number of dots on the left and the right half of the \(i\)-th domino, respectively. The dominoes are given in the order in which they must be laid out.

Output

Print TAK if the dominoes can be laid out correctly in the given order, or NI if this is impossible.

Constraints

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

\(0 \le a_i, b_i \le 6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 3 2 3 3 4 3	TAK

Input (stdin) сopy	Output (stdout) сopy
3 1 2 2 3 2 4	NI

Input (stdin) сopy	Output (stdout) сopy
1 0 6	TAK

Notes

In the first example, the second and the fourth dominoes can be flipped to get the following row:

The numbers of dots match at every joint.

In the second example, both joints next to the second domino need a half with 2 dots. The second domino has only one such half, so the row cannot be laid out correctly.

In the third example, there is only one domino, so the condition on adjacent dominoes holds.