题目描述

桌面上有依次排列的 $n$ 张卡片，每张卡片有正反两面。共 $m$ 次操作，每次操作会交换两张卡片，询问交换后是否有可能通过改变卡片的正反来使卡片上的数不降。

输入格式

第一行一个整数 $n$，表示卡片的数量。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示卡片的正反两面。

接下来 $m$ 行，第 $j$ 行有两个整数 $a_j,b_j$，表示第 $j$ 次操作交换第 $a$ 张和 $b$ 张卡片。

输出格式

输出 $m$ 行，第 $j$ 行表示第 $j$ 次操作后是否能使卡片上的数不降，输出一行字符串 "TAK" 或 "NIE"，分别表示可能、不可能。

样例

输入

4
2 5
3 4
6 3
2 7
2
3 4
1 3

输出

NIE
TAK

数据范围与提示

对于 $30\%$ 的数据，保证每张卡两面的数字相同。

对于 $38\%$ 的数据（可能不同），$n \le 2000$。

对于 $100\%$ 的数据，$2 \le n \le 200000$，$0 \le x_i,y_i \le 10^7$，$1 \le m \le 1000000$。

对于下方的三组样例：

• 1ocen：$n=6,m=6$，用于测试程序正确性。
• 2ocen：$n=7,m=9$，保证卡的两面数字相同。
• 3ocen：$n=200000,m=1000000$，所有偶数编号的操作反转其前一次操作。