You are given a sequence of positive integers a₁, a₂, . . . , a_n. We would like to order the numbers from 1 to n in such a way, that the i-th number is not greater than a_i (for each i). In other words, we are looking for a permutation p of numbers from 1 to n, which satisfies: p_i ≤ a_i for each 1 ≤ i ≤ n. There is one more problem, the sequence ai may change over time. . .

Input

The first line of standard input contains one integer n (1 ≤ n ≤ 200 000), the number of elements of the a_i sequence. In the second line, there is a sequence of n positive integers a_i (1 ≤ a_i ≤ n), separated by single spaces. The third line contains one integer m (0 ≤ m ≤ 500 000), representing the number of modifications made to the ai sequence. The following m lines describe these modifications. Each description consists of two integers j_i and w_i (1 ≤ j_i, w_i ≤ n for 1 ≤ i ≤ m), separated by single spaces and meaning that j_i-th element of the sequence becomes w_i. The operations take place in turns, so the i-th modification is applied to the sequence altered by (i − 1) previous modifications.

Output

Your program should output exactly m + 1 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 p, which satisfies p_i ≤ a_i for each i (for the original a_i sequence), whereas the words from following lines answer the question whether there exist any (potentially different) permutations that satisfy the given conditions for the ai sequence after each modification.

Example

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 ai sequence, the condition is satisfied by permutation 2, 4, 3, 1, 5. After the first modification, the sequence becomes 3, 4, 3, 2, 4 and for this sequence no valid permutation exists. After the second modification, the sequence is 5, 4, 3, 2, 4. An example of a permutation p satisfying all constraints for this sequence is 5, 1, 3, 2, 4.