시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 16 14 14 87.500%

문제

보드게임 카페에서 아르바이트를 하는 정기는 사장님 몰래 도미노 놀이를 하는 취미가 있다. 도미노 놀이는 줄지어 세운 도미노의 한쪽 끝을 밀어 다른 도미노들을 연속적으로 넘어트리는 놀이를 말하는데, 정기는 사장님이 가장 아끼는 숫자 도미노로 도미노 놀이를 하기 때문에 사장님에게 들키지 않으려 노력한다.

그러나, 어느 때와 마찬가지로 사장님 몰래 도미노 놀이를 즐기고 있던 정기는 도미노가 쓰러지는 모습을 넋 놓고 지켜보던 중 사장님에게 도미노 놀이를 하는 장면을 들키고 말았다.

자신의 숫자 도미노를 가지고 있는 정기를 보며 화를 내려던 사장님은 줄을 완벽하게 맞추며 쓰러진 숫자 도미노를 보고 정기에게 자신이 낸 질문을 모두 맞춘다면 이번 일은 눈감아 주겠다고 하였고, 숫자 도미노의 진정한 사용 방법을 알려주었다.

정기가 도미노 놀이에 사용한 숫자 도미노는 앞면과 뒷면에 같은 정수가 적혀있는데, 숫자 도미노를 통한 도미노 놀이는 이 숫자들을 이용하여 도미노의 숫자를 추측하는 방식으로 이루어진다.

첫 번째 도미노는 쓰러지며 두 번째 도미노를 덮고, 두 번째 도미노는 세 번째 도미노를 덮는다. 이런 식으로 i번째 도미노는 i+1번째 도미노를 덮는데, 질문자는 첫 번째 도미노부터 마지막의 바로 전 도미노까지 각각의 도미노와 도미노가 덮은 도미노의 수를 XOR한 값을 기록한다. 즉, 첫 번째 도미노 수와 두 번째 도미노 수의 XOR, 두 번째 도미노 수와 세 번째 도미노 수의 XOR, 이런 식으로 도미노의 개수 – 1 개의 숫자를 기록한다.

이후 쓰러진 도미노를 치운 뒤 질문자는 플레이어에게 기록한 숫자를 보여주고, 두 가지 종류의 질문을 한다.

  1. x번째 도미노의 수와 y번째 도미노의 수를 XOR한 값을 답하라.
  2. 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개의 줄에 걸쳐 출력한다.

예제 입력 1

5 5
1 2 3 4
0 1 2
0 1 3
1 1 2 3
1 3 5 5
0 1 1

예제 출력 1

1
3
2
2
0