桌上有 $n$ 张牌按一定顺序排列。每张牌的两面各写有一个整数：正面和反面。初始时，所有牌正面朝上。伟大的魔术师 Byteasar 打算（多次！）表演他的招牌“二分查找牌戏”。然而，为了表演成功，他需要牌面上的数字序列呈非递减顺序。因此，Byteasar 可能需要翻转某些牌，使反面的数字可见。

此外，魔术还需要一名观众参与。遗憾的是，一些志愿者是由 Byteasar 的竞争对手派来的，他们想让他失败。每一位这样的“冒牌”志愿者上台后，都会以迅雷不及掩耳之势交换桌上的两张牌。在每次交换后，Byteasar 可以再次翻转他想要的任何牌，但即便如此，他可能仍无法完成他的伟大魔术。如果发生这种情况，他将被迫转向传统的魔术，比如从帽子里变出一只兔子。

请编写一个程序，在每次交换牌后，判断 Byteasar 是否能够完成他的伟大魔术。

输入格式

标准输入的第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示牌的数量。接下来的 $n$ 行描述了桌上按顺序排列的牌。其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 10^7$)，由空格分隔。这些是第 $i$ 张牌上的数字：$x_i$ 是正面数字，$y_i$ 是反面数字。初始的牌序列可能无法完成伟大魔术。

随后的一行包含一个整数 $m$ ($1 \le m \le 1\,000\,000$)，表示交换牌的次数。接下来的 $m$ 行描述了交换操作：第 $j$ 行包含两个整数 $a_j$ 和 $b_j$ ($1 \le a_j, b_j \le n$)，由空格分隔，表示第 $j$ 位（冒牌）志愿者交换了第 $a_j$ 张牌和第 $b_j$ 张牌。

输出格式

程序应向标准输出打印 $m$ 行，每行包含一个单词：TAK（波兰语，意为“是”）或 NIE（波兰语，意为“否”）。如果 Byteasar 在第 $j$ 次交换后可以通过翻转牌获得非递减序列，则第 $j$ 行应输出 TAK；如果不能，则输出 NIE。

样例

输入 1

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

输出 1

NIE
TAK