In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

<Submit a solution> [0/100]**Task statistics**

Number of users: 262

Number of users with 100 points: 184

Average result: 79.9618

# Cards

### Memory limit: 64 MB

## Input

## Output

## Example

Number of users: 262

Number of users with 100 points: 184

Average result: 79.9618

There are cards arranged on a table in a certain order. Two integers are written on each card, one per side: the obverse and the reverse. Initially all cards lie with the averse facing up. Byteasar, The Great Illusionist, intends to perform (multiple times!) his signature Binary Search Card Manipulation. However, to present it, he needs the sequence of numbers as seen on the cards to be non-decreasing. Thus, Byteasar may have to turn over some cards so that the numbers on their reverse sides become visible.

Furthermore, the illusion requires a participant from the audience. Alas, some of the volunteers are deployed by Byteasar's competitors who want him to fail. Each such supposititious volunteer, upon entering the scene, would swap two cards on the table in a lightning move of a hand. After each such swap, Byteasar can again turn over any cards he desires but nevertheless, he may not be able to perform his great illusion. If that were to happen, he would be forced to turn to traditional illusions, such as pulling a rabbit out of a hat.

Write a program that determines, after each card swap, if Byteasar can perform his great illusion.

In the first line of the standard input, there is a single integer, (), the number of the cards. The lines that follow describe the cards, one per line, in the order they are arranged on the table. The -th of these lines has two integers and (), separated by a single space. These are the numbers written on the -th card: is the one written on the obverse and the one on the reverse. The initial sequence of cards may not allow performing the great illusion.

Afterwards, there is a line with a single integer (), the number of card swaps. The lines that follow describe the swaps: -th of these lines has two integers and (), separated by a single space, indicating that the -th (supposititious) volunteer will swap the -th and the -th cards.

In tests worth 30% of the whole score, the following condition holds: for each card, the numbers on both its sides are equal. In (possibly different) tests worth 38% of the whole score, the condition holds.

Your program should print lines to the standard output, each containing a single word:
`TAK` (Polish for *yes*) or `NIE` (Polish for *no*).
The -th line should read `TAK` if Byteasar can obtain a non-decreasing sequence
of numbers by turning the cards over after the -th card swap. If he cannot,
the line should read `NIE`.

For the input data:

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

the correct result is:

NIE TAK

**Sample grading tests:**

`1ocen:`, , small correctness test,`2ocen:`, , numbers on both sides of each card are equal,`3ocen:`, , each even-numbered swap reverts the one preceding it.

*Task author: Adam Polak.*