Description

There are $n$ cards arranged on a table in a fixed order.

Each card has two integers, one on each side: the obverse and the reverse. The $i$-th card has $x_i$ on the obverse and $y_i$ on the reverse. Initially, all cards lie with the obverse side up.

Byteasar, the Great Illusionist, wants the sequence of visible numbers on the cards to be non-decreasing. He may flip any subset of cards to show the other side.

However, an audience participant will repeatedly swap two cards on the table. After each such swap, Byteasar may again flip any cards, but he might still be unable to achieve a non-decreasing sequence. After each swap, determine whether it is possible to obtain a non-decreasing sequence of visible numbers by flipping cards as needed.

Input Format

The first line contains a single integer $n$ ($2 \le n \le 200\ 000$), the number of cards.

The next $n$ lines describe the cards, in their current order 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 a single space, where $x_i$ is written on the obverse and $y_i$ on the reverse of the $i$-th card.

The initial sequence of cards may not allow forming a non-decreasing sequence.

Afterwards, there is a line with a single integer $m$ ($1 \le m \le 1\ 000\ 000$), the number of card swaps. The next $m$ lines describe the swaps: the $j$-th of these lines has two integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le n$), indicating that the $j$-th participant swaps the $a_j$-th and $b_j$-th cards.

Output Format

Print $m$ lines. On the $j$-th line, print TAK (Polish for yes) if, after the $j$-th swap, Byteasar can obtain a non-decreasing sequence of visible numbers by flipping any subset of cards; otherwise, print NIE (Polish for no).

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

NIE
TAK

Hint

There are several cards, each with a number on both sides. You may flip any cards. Each operation swaps two cards’ positions. After each operation, determine whether, with the current card order, flipping some cards can form a non-decreasing sequence.

Translated by ChatGPT 5