Cards

There are $n$ cards laid out in a row on a table. Each card has one integer written on its obverse and one on its reverse, and every card starts with its obverse facing up.

Byteasar the great illusionist wants to perform his signature trick, Binary Search Card Manipulation, several times. The trick works only when the numbers facing up are non-decreasing from left to right, so Byteasar may turn over some cards to expose the numbers on their reverse sides.

The trick also needs a volunteer from the audience. Some volunteers are planted by Byteasar's competitors, and each of them swaps two cards on the table with one quick move of a hand the moment he steps on stage. After a swap Byteasar may again turn over any cards he wants, yet he still might not be able to perform the trick.

Write a program that decides, after every swap, whether Byteasar can perform the trick.

The first line contains the number of cards $n$ ($2 \le n \le 200000$). Each of the next $n$ lines describes one card, in the order the cards lie on the table. The $i$-th of these lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^7$) separated by one space. $x_i$ is written on the obverse of the $i$-th card and $y_i$ on its reverse. The starting arrangement is not guaranteed to allow the trick.

The next line contains the number of swaps $m$ ($1 \le m \le 1000000$). Each of the next $m$ lines describes one swap, in the order the swaps happen. The $j$-th of these lines contains two integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le n$) separated by one space, meaning that the $j$-th volunteer exchanges the cards at positions $a_j$ and $b_j$. Every swap acts on the arrangement left by all earlier swaps. If $a_j$ equals $b_j$, the arrangement does not change.

Print $m$ lines. Line $j$ contains TAK if Byteasar can turn cards over so that the visible numbers are non-decreasing after the $j$-th swap, and NIE otherwise. The set of turned cards may be chosen anew after each swap. TAK and NIE are Polish for yes and no.