题目描述

有 $n$ 张卡片在桌上一字排开，每张卡片上有两个数，第 $i$ 张卡片上，正面的数为 $a_i$，反面的数为 $b_i$。现在，有 $m$ 个熊孩子来破坏你的卡片了！

第 $i$ 个熊孩子会交换 $c_i$ 和 $d_i$ 两个位置上的卡片。

每个熊孩子捣乱后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面变成正面，但不能改变卡片的位置），能否让卡片正面上的数从左到右单调不降。

输入格式

第一行一个 $n$。

接下来 $n$ 行，每行两个数 $a_i,b_i$。

接下来一行一个 $m$。

接下来 $m$ 行，每行两个数 $c_i,d_i$。

输出格式

$m$ 行，每行对应一个答案。如果能成功，输出 TAK，否则输出 NIE。

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

NIE
TAK

样例解释

交换 $3$ 和 $4$ 后，卡片序列为 $(2,5)~(3,4)~(2,7)~(6,3)$，不能成功。

交换 $1$ 和 $3$ 后，卡片序列为 $(2,7)~(3,4)~(2,5)~(6,3)$，翻转第 $3$ 张卡片，卡片的正面为 $2,3,5,6$，可以成功。

数据范围

$n \le 2 \times 10^5, m \le 10 ^ 6, 0 \le a_i,b_i \le 10^7, 1 \le c_i,d_i \le n$

题目来源

By Dzy