길이가 $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$)

둘째 줄에는 $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$번 쿼리의 결과를 출력한다.

Sample

Input

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

Output

TAK
TAK
TAK
NIE