XORanges

Janez는 오렌지를 좋아한다. 그래서 오렌지 스캐너를 만들었다. 카메라와 Raspberry Pi 3b+ 컴퓨터로 오렌지의 3D 이미지를 만들기 시작했다. 이미지 프로세서의 성능이 좋지 않아서, 얻을 수 있는 출력은 껍질의 구멍에 대한 정보를 담은 32비트 정수 하나뿐이다. 32비트 정수 D는 0 또는 1인 32개의 숫자(비트)의 나열로 표현된다. 0에서 시작해 1인 i번째 비트마다 2i를 더하면 D를 얻을 수 있다. 더 형식적으로, D = d31·231 + d30·230 + ... + d1·21 + d0·20일 때 수 D는 수열 d31, d30, ..., d0으로 표현된다. 예를 들어 13은 0, ..., 0, 1, 1, 0, 1로 표현된다.

Janez는 n개의 오렌지를 스캔했다. 하지만 프로그램이 실행되는 동안 가끔 오렌지 하나(i번째 오렌지)를 다시 스캔하기로 한다. 그러면 그 스캔 이후로는 i번째 오렌지에 갱신된 값을 사용한다.

Janez는 이 오렌지들을 분석하려 한다. 그는 배타적 논리합(XOR) 연산에 흥미를 느껴 몇 가지 계산을 하려 한다. 오렌지의 범위 l부터 u까지(l ≤ u)를 고르고, 그 범위의 모든 원소, 그 범위의 모든 연속한 두 원소 쌍, 모든 연속한 세 원소의 수열, 이런 식으로 u - l + 1개의 연속한 원소(범위의 모든 원소)의 수열까지의 XOR 값을 구하려 한다.

즉, l = 2, u = 4이고 스캔한 값의 배열이 A라면, 프로그램은 a2 ⊕ a3 ⊕ a4 ⊕ (a2 ⊕ a3) ⊕ (a3 ⊕ a4) ⊕ (a2 ⊕ a3 ⊕ a4)의 값을 반환해야 한다. 여기서 ⊕는 XOR을, ai는 배열 A의 i번째 원소를 나타낸다.

XOR 연산은 다음과 같이 정의한다.

첫 번째 값의 i번째 비트가 두 번째 값의 i번째 비트와 같으면 결과의 i번째 비트는 0이다. 첫 번째 값의 i번째 비트가 두 번째 값의 i번째 비트와 다르면 결과의 i번째 비트는 1이다.

입력의 첫 줄에 두 양의 정수 n과 q(다시 스캔과 질의, 즉 전체 동작의 수)가 주어진다.

다음 줄에 n개의 공백으로 구분된 음이 아닌 정수가 주어지며, 배열 A의 값(오렌지 스캔 결과)을 나타낸다. 원소 ai는 i번째 오렌지의 값을 담는다. 인덱스 i는 1부터 시작한다.

다음 q개의 줄에 동작이 세 개의 공백으로 구분된 양의 정수로 설명된다.

동작 유형이 1(다시 스캔)이면 첫 번째 정수는 1이고, 이어서 i(Janez가 다시 스캔하려는 오렌지의 인덱스)와 j(i번째 오렌지를 다시 스캔한 결과)가 주어진다.

동작 유형이 2(질의)이면 첫 번째 정수는 2이고, 이어서 l과 u가 주어진다.

각 질의마다 그 질의에 맞는 결과 정수를 정확히 하나씩 출력한다. 모든 값을 새 줄에 출력한다. i번째 출력 줄은 i번째 질의의 결과와 일치해야 한다.

• ai ≤ 109
• 0 < n, q ≤ 2·105