在拜特城（Bajtocja）正在举办一年一度的机器人大赛，共有 $n$ 个机器人参赛，编号从 $1$ 到 $n$。第 $i$ 个机器人由两个参数 $s_i$ 和 $z_i$（$1 \le s_i, z_i \le n$）描述，分别代表其力量和敏捷度。已知所有 $s_i$ 两两不同，所有 $z_i$ 也两两不同。

比赛由一系列对决组成。在每一场对决中，两名尚未被淘汰的机器人进行比赛。在第 $i$ 个机器人与第 $j$ 个机器人的对决中，如果 $s_i > s_j$ 或 $z_i > z_j$，则前者淘汰后者；同样地，如果 $s_i < s_j$ 或 $z_i < z_j$，则后者淘汰前者。注意，这意味着在同一场对决中，两名机器人可能同时被淘汰。如果某个机器人在对决中没有被淘汰，它还可以参加后续的对决。

当所有机器人最终都被淘汰时，比赛的转播收视率最高。你的任务是判断是否可以通过安排一系列对决，使得所有机器人最终都被淘汰。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）。 接下来的 $n$ 行描述机器人。第 $i$ 个机器人的描述（对于 $1 \le i \le n$）包含两个整数 $s_i, z_i$（$1 \le s_i, z_i \le n$）。 你可以假设 $s_1, s_2, \dots, s_n$ 两两不同，且 $z_1, z_2, \dots, z_n$ 也两两不同。

输出格式

如果可以通过安排对决使得所有机器人最终都被淘汰，则输出 TAK，否则输出 NIE。

样例

输入格式 1

4
1 4
2 2
3 3
4 1

输出格式 1

TAK

说明

我们有 $s_1 = 1, z_1 = 4, s_2 = 2, z_2 = 2, s_3 = 3, z_3 = 3, s_4 = 4, z_4 = 1$。例如，如果第一场对决由前两个机器人参加，第二场对决由后两个机器人参加，那么所有机器人都会被淘汰。

输入格式 2

2
1 1
2 2

输出格式 2

NIE

样例测试

样例测试包含上述示例。此外：

• 1ocen: $n = 8, s_i = i, z_i = n - i + 1$（对于所有 $1 \le i \le n$）。答案为 TAK。
• 2ocen: $n = 20$，且存在一个机器人可以击败所有其他机器人，同时没有机器人能击败它。答案为 NIE。
• 3ocen: $n = 500$，且所有机器人可以两两配对，使得每对机器人都能互相淘汰。答案为 TAK。
• 4ocen: $n = 200\,000, s_i = i, z_i = i$（对于 $1 \le i \le \frac{n}{2}$），以及 $s_i = i, z_i = \frac{3n}{2} - i + 1$（对于 $\frac{n}{2} < i \le n$）。答案为 TAK。
• 5ocen: $n = 5$，小型正确性测试。答案为 TAK。

子任务