長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。以下のクエリを処理するプログラムを作成せよ。

• 1 x v: $A_x$ を $v$ に変更する。

• 2 k b_1 ... b_k: 数列 $A$ を以下の条件を満たす区間に分割できるならば "TAK" を、そうでなければ "NIE" を出力する。

  • 各要素はちょうど一つの区間に属する。
  • 区間は重なってはならない。
  • 各区間内の全ての数の XOR が $b_1, \ldots, b_k$ のいずれかに等しくなければならない。

入力

最初の行には数列の長さ $N$ が含まれる。($1 \le N \le 100{,}000$)

2 行目には $A_1, A_2, \ldots, A_N$ が含まれる。($0 \le A_i < 2^{20}$)

3 行目にはクエリの個数 $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