xor 쿼리

면접 대비

시간 제한2초메모리 제한1024 MB

요약

배열의 값을 바꾸는 쿼리가 주어질 때, 모든 원소에 x를 XOR한 배열에서 i번째로 큰 값을 구합니다.

문제

길이가 $N$ 인 정수 수열 $a=[a_1,a_2,\ldots,a_N]$ 이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

$1$ $i$ $x$ : $a_i$ 의 값을 $x$ 로 변경한다.
$2$ $i$ $x$ : 수열 $[a_1\oplus x,a_2\oplus x,\ldots,a_N\oplus x]$ 에서 중복을 포함하여 $i$ 번째로 큰 값을 출력한다.

여기서 $a\oplus b$ 는 $a$ 와 $b$ 의 비트 단위 배타적 논리합(bitwise xor) 연산을 의미한다.

첫 번째 줄에 수열 $a$ 의 길이 $N$ 이 주어진다. $(1\le N\le 100\,000)$

두 번째 줄에 $N$ 개의 정수 $a_1,a_2,\ldots,a_N$ 이 공백으로 구분되어 주어진다. $(0\le a_i\le 2^{31}-1)$

세 번째 줄에 쿼리의 수 $Q$ 가 주어진다. $(1\le Q\le 100\,000)$

네 번째 줄부터 $Q$ 개의 줄에 걸쳐 쿼리가 주어진다. 2번 쿼리는 한 번 이상 주어진다. $(1\le i\le N;\ 0\le x\le 2^{31}-1)$

2번 쿼리마다 결괏값을 한 줄에 하나씩 출력한다.

예제 1

입력

9
1 2 3 4 5 6 7 8 9
11
2 1 7
2 2 7
2 3 7
1 1 3
1 2 3
1 4 3
2 1 12
2 2 12
2 3 12
2 4 12
2 5 12

예상 출력