In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
You are given a sequence of positive integers , , ..., . We would like to order the numbers from to in such a way, that the -th number is not greater than (for each ). In other words, we are looking for a permutation of numbers from to , which satisfies: for each . There is one more problem, the sequence may change over time...
The first line of standard input contains one integer (), the number of elements of the sequence. In the second line, there is a sequence of positive integers (), separated by single spaces. The third line contains one integer (), representing the number of modifications made to the sequence. The following lines describe these modifications. Each description consists of two integers and ( for ), separated by single spaces and meaning that -th element of the sequence becomes . The operations take place in turns, so the -th modification is applied to the sequence altered by previous modifications.
Your program should output exactly lines to the standard output. Each of those lines should contain one word TAK (meaning YES) or NIE (meaning NO). The word in the first line should tell if there exists a permutation , which satisfies for each (for the original sequence), whereas the words from following lines answer the question whether there exist any (potentially different) permutations that satisfy the given conditions for the sequence after each modification.
For the input data:
5 3 4 3 2 5 2 5 4 1 5
the correct result is:
TAK NIE TAK
Explanation of the example. For the original sequence, the condition is satisfied by permutation . After the first modification, the sequence becomes and for this sequence no valid permutation exists. After the second modification, the sequence is . An example of a permutation satisfying all constraints for this sequence is .
Task author: Jakub Radoszewski.