도미노 예측
면접 대비시간 제한1초메모리 제한256 MB
연속한 도미노 번호의 XOR 값들이 주어질 때, x번과 y번의 XOR을 구하거나 x번이 d일 때 y번 값을 구하는 질의에 답한다.
문제
보드게임 카페에서 아르바이트를 하는 정기는 사장님 몰래 도미노 놀이를 즐긴다. 도미노 놀이는 줄지어 세운 도미노의 한쪽 끝을 밀어 다른 도미노를 연속으로 넘어뜨리는 놀이인데, 정기는 사장님이 가장 아끼는 숫자 도미노로 놀이를 하므로 사장님에게 들키지 않으려 애쓴다.
그런데 어느 날 사장님 몰래 도미노 놀이를 하던 정기는 도미노가 쓰러지는 모습을 넋 놓고 지켜보다가 사장님에게 들키고 만다.
자기 숫자 도미노를 가진 정기를 보며 화를 내려던 사장님은 줄이 완벽하게 맞으며 쓰러진 숫자 도미노를 보고, 자신이 내는 질문을 모두 맞히면 이번 일은 눈감아 주겠다고 하면서 숫자 도미노의 진짜 사용법을 알려준다.
정기가 도미노 놀이에 사용한 숫자 도미노는 앞면과 뒷면에 같은 정수가 적혀 있다. 숫자 도미노를 이용한 도미노 놀이는 이 숫자로 도미노의 수를 추측하는 방식으로 진행된다.
첫 번째 도미노는 쓰러지면서 두 번째 도미노를 덮고, 두 번째 도미노는 세 번째 도미노를 덮는다. 이런 식으로 i번째 도미노는 i+1번째 도미노를 덮는다. 질문자는 첫 번째 도미노부터 마지막 바로 전 도미노까지 각 도미노의 수와 그 도미노가 덮은 도미노의 수를 XOR한 값을 기록한다. 즉 첫 번째 도미노의 수와 두 번째 도미노의 수의 XOR, 두 번째 도미노의 수와 세 번째 도미노의 수의 XOR 하는 식으로 도미노 개수 - 1개의 수를 기록한다.
그다음 쓰러진 도미노를 치운 뒤 질문자는 플레이어에게 기록한 수를 보여주고 두 가지 질문을 한다.
- x번째 도미노의 수와 y번째 도미노의 수를 XOR한 값을 답하라.
- x번째 도미노의 수가 d일 때, y번째 도미노의 수를 답하라.
숫자 도미노 놀이가 처음인 정기를 위해 사장님의 질문에 대신 답해 줄 프로그램을 작성해 보자.
입력
첫 번째 줄에 숫자 도미노의 개수 N과 질문의 수 Q가 정수로 주어진다. (3 ≤ N ≤ 2 × 105, 1 ≤ Q ≤ 105)
두 번째 줄에 사장님이 기록한 N-1개의 정수가 주어진다. (각 정수는 0 이상 231-1 이하이다.)
세 번째 줄부터 Q개의 줄에 걸쳐 사장님의 질문이 한 줄에 하나씩 주어진다. 질문의 형식은 “0 x y” 또는 “1 x y d”이고, 순서대로 1번 질문과 2번 질문을 뜻한다. (1 ≤ x ≤ y ≤ N, 0 ≤ d ≤ 231-1)
출력
주어진 질문의 답을 Q개의 줄에 걸쳐 출력한다.