You are given a sequence of positive integers $a_{1}, a_{2}, ..., 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 Format

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 $a_{i}$ 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 Format

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 ai 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

Input

5
3 4 3 2 5
2
5 4
1 5

Output

TAK
NIE
TAK

For the original $a_{i}$ 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.