Under construction

Still being built. Things may change

Sequence and Queries 32

Time limit10sMemory limit512 MB

Summary
Maintain a sequence under point updates and answer whether it can be split into contiguous blocks whose xors all lie in a small given set.
Level

Hard9 of 10

Topics
Dynamic programming, Prefix sum, Bit manipulation, Segment tree
Solved
No attempts yet

Problem

A sequence A1,A2,…,ANA_1, A_2, \ldots, A_N of length NN is given. Write a program that performs the following queries.

  • 1 x v: replace AxA_x with vv.

  • 2 k b1 ... bk: if the sequence AA can be partitioned into intervals satisfying the conditions below, print "TAK"; otherwise print "NIE".

    • Every element must belong to exactly one interval.
    • The intervals must not overlap.
    • The xor of all elements in each interval must equal one of b1,…,bkb_1, \ldots, b_k.

Input

The first line contains the size of the sequence, NN. (1≤N≤100,0001 \le N \le 100,000)

The second line contains A1,A2,…,ANA_1, A_2, \ldots, A_N. (0≤Ai<2200 \le A_i < 2^{20})

The third line contains the number of queries, MM. (1≤M1 \le M)

Each of the next MM lines contains one query. (1≤x≤N1 \le x \le N, 0≤v,bi<2200 \le v, b_i < 2^{20}, 1≤k≤51 \le k \le 5)

The number of type 1 queries does not exceed 400,000, and the sum of kk over all type 2 queries does not exceed 100,000.

Output

Print the result of each type 2 query.

Examples1

  1. Example 1

    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
    Expected output
    TAK
TAK
TAK
NIE