长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$ 给定。请编写一个程序执行以下查询：

• 1 x v：将 $A_x$ 改为 $v$。

• 2 k b_1 ... b_k：如果可以将数列 $A$ 分割成满足以下条件的区间，则输出 "TAK"，否则输出 "NIE"。

  • 每个数必须恰好包含在一个区间中。
  • 区间不能重叠。
  • 每个区间内所有数的异或结果必须等于 $b_1, \ldots, b_k$ 中的一个。

输入格式

第一行包含数列的长度 $N$。($1 \le N \le 100{,}000$)

第二行包含 $A_1, A_2, \ldots, A_N$。($0 \le A_i < 2^{20}$)

第三行包含查询的个数 $M$。($1 \le M$)

接下来 $M$ 行中，每行给出一个查询。($1 \le x \le N$, $0 \le v, b_i < 2^{20}$, $1 \le k \le 5$)

类型 1 的查询个数不超过 $400{,}000$，类型 2 的查询中给出的 $k$ 的总和不超过 $100{,}000$。

输出格式

输出类型 2 的查询的结果。

样例

样例输入 1

5
1 2 0 3 0
10
2 1 3
2 1 0
1 3 5
2 2 6 3
1 1 8
1 2 5
1 3 3
1 4 1
1 5 1
2 3 2 4 8

样例输出 1

TAK
TAK
TAK
NIE