题目描述

有 $n$ 张卡牌，正反各有一个数，分别为 $x_i$ 与 $y_i$。

有 $m$ 次操作，每次操作会交换两张卡牌，你需要在每次操作后回答是否可能通过翻转卡牌，使得正面朝上的数形成一个单调不降序列。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 张卡牌上的两个数。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行两个整数 $a,b$，表示本次操作交换第 $a$ 张与第 $b$ 张卡牌。

输出格式

输出 $m$ 行，如果第 $i$ 次操作后可能达到目标，输出 TAK，否则输出 NIE。

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

NIE
TAK

提示

$1 \le n \le 2 \times 10^5$，$1 \le m \le 10^6$，$1 \le x_i,y_i \le 10^7$，$1 \le a,b \le n$。