cho.shXOR 놀이
아직 제출이 없습니다시간 제한3초메모리 제한512 MB문제 설명
예제1
문제
재현이와 준혁이가 요즘 가장 즐겨 하는 놀이는 XOR놀이다.
XOR놀이란, 배열 A가 주어질 때 다음과 같은 쿼리를 처리하는 놀이이다.
- 1 l r x : l≤i≤r 를 만족하는 i중 x와 A_i 를 XOR한 수가 가장 작은 수 A_i를 골라 그 i를 출력한다. 만약 그런 i가 여러 개 있다면, 가장 작은 것을 출력한다.
- 2 l r x : l≤i≤r 를 만족하는 i중 x와 A_i 를 XOR한 수가 가장 큰 수 A_i를 골라 그 i를 출력한다. 만약 그런 i가 여러 개 있다면, 가장 작은 것을 출력한다.
- 3 p x : A_p 를 x 로 바꾼다.
재현이와 준혁이를 위해 XOR놀이를 진행해주는 프로그램을 만들어보자!
입력
첫째 줄에 처음 배열의 크기 N이 입력된다. (1≤N≤100,000)
둘째 줄에 처음 배열의 원소 A_i가 N개 입력된다. (0≤A_i≤107)
셋째 줄에 쿼리의 수 Q가 입력된다. (1≤Q≤50,000)
다음 Q개의 줄에는 쿼리가 입력된다. (0≤x≤107, 1≤l≤r≤N, 1≤p≤N)
출력
각 1,2번 쿼리마다 쿼리의 답을 한 줄에 하나씩 입력된 순서대로 출력한다.