XOR 놀이

시간 제한3초메모리 제한512 MB

요약

배열의 원소를 바꾸는 갱신이 있을 때, 구간 안에서 x와 XOR한 값이 가장 작거나 큰 원소의 인덱스를 구합니다. 동점이면 가장 작은 인덱스를 출력합니다.

문제

재현이와 준혁이가 요즘 가장 즐겨 하는 놀이는 XOR 놀이다.

XOR 놀이에서는 배열 $A$ 가 주어졌을 때 다음 쿼리를 처리한다.

1 $l$ $r$ $x$ : $l \le i \le r$ 을 만족하는 $i$ 중에서 $x$ 와 $A_i$ 를 XOR한 값이 가장 작은 $A_i$ 를 고르고, 그 $i$ 를 출력한다. 그런 $i$ 가 여러 개라면 가장 작은 $i$ 를 출력한다.
2 $l$ $r$ $x$ : 같은 조건에서 XOR한 값이 가장 큰 $A_i$ 를 고르고, 그 $i$ 를 출력한다. 그런 $i$ 가 여러 개라면 가장 작은 $i$ 를 출력한다.
3 $p$ $x$ : $A_p$ 를 $x$ 로 바꾼다.

재현이와 준혁이를 위해 XOR 놀이를 진행하는 프로그램을 만들어보자!

첫째 줄에 배열의 크기 $N$ 이 주어진다. $(1 \le N \le 100,000)$

둘째 줄에 배열의 원소 $A_i$ 가 $N$ 개 주어진다. $(0 \le A_i \le 10^7)$

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

다음 $Q$ 개의 줄에 쿼리가 주어진다. $(0 \le x \le 10^7$ , $1 \le l \le r \le N$ , $1 \le p \le N)$

1번과 2번 쿼리마다 답을 입력된 순서대로 한 줄에 하나씩 출력한다.

예제 1

입력

7
92 104 100 43 28 108 97
9
2 2 6 76
1 3 4 66
2 6 7 6
3 6 16
2 6 6 101
1 7 7 69
3 6 6
2 1 3 108
1 5 5 124

예상 출력