카드

탁자 위에 카드 $n$장이 일렬로 놓여 있다. 카드마다 앞면과 뒷면에 정수가 하나씩 적혀 있고, 처음에는 모든 카드가 앞면을 위로 향한 채 놓여 있다.

위대한 마술사 비테아사르는 자신의 대표 마술인 이진 탐색 카드 조작을 여러 번 선보이려 한다. 이 마술은 위를 향한 면에 적힌 수가 왼쪽부터 오른쪽까지 감소하지 않을 때만 성립한다. 그래서 비테아사르는 카드 몇 장을 뒤집어 뒷면의 수가 보이게 만들 수 있다.

마술에는 관객 한 명이 필요한데, 지원자 중 일부는 비테아사르를 실패시키려는 경쟁자가 심어 둔 사람이다. 이런 지원자는 무대에 오르자마자 손을 재빠르게 놀려 카드 두 장의 자리를 맞바꾼다. 자리가 바뀐 뒤에도 비테아사르는 원하는 카드를 다시 마음대로 뒤집을 수 있지만, 그래도 마술을 하지 못할 수 있다.

교환이 한 번 일어날 때마다 비테아사르가 마술을 할 수 있는지 판정하는 프로그램을 작성하시오.

첫째 줄에 카드의 개수 $n$ ($2 \le n \le 200000$)이 주어진다. 다음 $n$개 줄에는 탁자에 놓인 순서대로 카드가 하나씩 주어진다. 그중 $i$번째 줄에는 두 정수 $x_i$와 $y_i$ ($0 \le x_i, y_i \le 10^7$)가 공백 하나로 구분되어 주어진다. $x_i$는 $i$번째 카드의 앞면에, $y_i$는 뒷면에 적힌 수이다. 처음 놓인 상태에서 마술을 할 수 있다는 보장은 없다.

그다음 줄에 교환 횟수 $m$ ($1 \le m \le 1000000$)이 주어진다. 다음 $m$개 줄에는 교환이 일어나는 순서대로 하나씩 주어진다. 그중 $j$번째 줄에는 두 정수 $a_j$와 $b_j$ ($1 \le a_j, b_j \le n$)가 공백 하나로 구분되어 주어지며, $j$번째 지원자가 $a_j$번 자리의 카드와 $b_j$번 자리의 카드를 맞바꾼다는 뜻이다. 각 교환은 그 앞의 교환을 모두 적용한 배치에 이어서 일어난다. $a_j$와 $b_j$가 같으면 배치는 그대로다.

$m$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 교환이 끝난 뒤 카드를 뒤집어서 보이는 수를 감소하지 않는 수열로 만들 수 있으면 TAK을, 만들 수 없으면 NIE를 출력한다. 뒤집을 카드는 교환마다 새로 고를 수 있다. TAK과 NIE는 폴란드어로 각각 긍정과 부정을 뜻한다.