시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 16 6 3 50.000%

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 

  • 1 x v: Ax를 v로 바꾼다.
  • 2 k b1 ... bk: 수열 A를 다음 조건을 만족하는 구간으로 나눌 수 있으면 "TAK", 아니면 "NIE"를 출력한다.
    • 각각의 수는 하나의 구간에 포함되어 있어야 한다.
    • 구간은 겹칠 수 없다.
    • 각 구간에 들어있는 모든 수를 xor한 결과는 b1, ..., bk 중 하나와 같아야 한다.

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (0 ≤ Ai < 220)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M)

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ x ≤ N, 0 ≤ v, bi < 220, 1 ≤ k ≤ 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

출처