25431번 - XOR 놀이 서브태스크

문제

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

XOR놀이란, 배열 $A$가 주어질 때 다음과 같은 쿼리를 처리하는 놀이이다.

• 1 $l$ $r$ $x$ : $l \leq i \leq r$ 를 만족하는 $i$중 $x$와 $A_i$ 를 XOR한 수가 가장 작은 수 $A_i$를 골라 그 $i$를 출력한다. 만약 그런 $i$가 여러 개 있다면, 가장 작은 것을 출력한다.
• 2 $l$ $r$ $x$ : $l \leq i \leq r$ 를 만족하는 $i$중 $x$와 $A_i$ 를 XOR한 수가 가장 큰 수 $A_i$를 골라 그 $i$를 출력한다. 만약 그런 $i$가 여러 개 있다면, 가장 작은 것을 출력한다.
• 3 $p$ $x$ : $A_p$ 를 $x$ 로 바꾼다.

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

입력

첫째 줄에 처음 배열의 크기 $N$이 입력된다. $(1 \leq N \leq 100,000)$

둘째 줄에 처음 배열의 원소 $A_i$가 $N$개 입력된다. $(0 \leq A_i​ \leq 10^7)$

셋째 줄에 쿼리의 수 $Q$가 입력된다. $(1 \leq Q \leq 50,000)$

다음 $Q$개의 줄에는 쿼리가 입력된다. $(0 \leq x \leq 10^7,ドル 1ドル \leq l \leq r \leq N,ドル 1ドル \leq p \leq N)$

출력

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

제한

서브태스크

힌트