Lost String

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka has a string consisting of characters A, B, and C.

First, for every three adjacent characters, she calculated which character appears most frequently among them, and recorded how many times this character appears. After that, she obtained a sequence in which each value is from 1 to 3. Then she decided to write down pairs (\(a_i\), \(b_i\)), which mean that the sequence contained \(b_1\) values of \(a_1\), then \(b_2\) values of \(a_2\), and so on.

Marichka told Zenik which pairs of numbers she obtained, and the boy became curious whether there actually exists such a string that can form these pairs.

For example, if Marichka initially has the string CABBBCAB, she will first write down the sequence [1, 2, 3, 2, 1, 1], because among the characters CAB all characters appear 1 time, among the characters ABB the character B appears 2 times, among the characters BBB the character B appears 3 times, and so on. Thus, Marichka writes down the following pairs: [(1, 1), (2, 1), (3, 1), (2, 1), (1, 2)].

Input

The first line contains a single integer \(k\) — the number of pairs. The next \(k\) lines each contain 2 integers \(a_i\) and \(b_i\).

Output

Print TAK if there exists a string that forms the given pairs, or NI otherwise.

Constraints

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

\(1 \le a_i \le 3\), \(a_i \ne a_{i+1}\),

\(1 \le b_i \le 10^9\).

Samples