给定一个正整数序列 $a_{1}, a_{2}, ..., a_{n}$。我们希望将 $1$ 到 $n$ 的数字进行排列，使得第 $i$ 个数字不超过 $a_{i}$（对于每个 $i$）。换句话说，我们要寻找一个 $1$ 到 $n$ 的排列 $p$，满足对于每个 $1 ≤ i ≤ n$，都有 $p_{i} ≤ a_{i}$。此外，序列 $a_{i}$ 可能会随时间发生变化。

输入格式

第一行包含一个整数 $n$ ($1 ≤ n ≤ 200\,000$)，表示序列 $a_{i}$ 的元素个数。第二行包含 $n$ 个正整数 $a_{i}$ ($1 ≤ a_{i} ≤ n$)，由空格分隔。第三行包含一个整数 $m$ ($0 ≤ m ≤ 500\,000$)，表示对序列 $a_{i}$ 进行的修改次数。接下来的 $m$ 行描述这些修改。每行包含两个整数 $j_{i}$ 和 $w_{i}$ ($1 ≤ j_{i}, w_{i} ≤ n$)，由空格分隔，表示将序列的第 $j_{i}$ 个元素修改为 $w_{i}$。这些操作按顺序执行，即第 $i$ 次修改是在经过前 $i-1$ 次修改后的序列基础上进行的。

输出格式

程序应向标准输出输出 $m+1$ 行。每一行应包含一个单词 TAK（表示是）或 NIE（表示否）。第一行应回答对于原始序列 $a_{i}$ 是否存在满足 $p_{i} ≤ a_{i}$ 的排列 $p$，后续各行则回答在每次修改后，对于当前的序列 $a_{i}$ 是否存在（可能不同的）满足条件的排列。

样例

输入 1

5
3 4 3 2 5
2
5 4
1 5

输出 1

TAK
NIE
TAK

说明 1

对于原始序列 $a_{i}$，排列 2, 4, 3, 1, 5 满足条件。第一次修改后，序列变为 3, 4, 3, 2, 4，对于该序列不存在合法的排列。第二次修改后，序列变为 5, 4, 3, 2, 4。满足该序列所有约束的一个排列 $p$ 为 5, 1, 3, 2, 4。