시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB75444260.000%

문제

Janez loves oranges! So he made a scanner for oranges. With a cameras and a Raspberry Pi 3b+ computer, he started creating 3D images of oranges. His image processor is not a very good one, so the only output he gets is a 32-bit integer, which holds information about the holes on the peel. A 32- bit integer D is represented as a sequence of 32 digits (bits) each of which is one or zero. If we start from 0 we can obtain D by adding 2i for every i-th bit that is equal to one. More formally the number D is represented by the sequence d31, d30, ..., d0 when D = d31·231 + d30·230 + ... + d1·21 + d0·20. For example, 13 is represented as 0, ..., 0, 1, 1, 0, 1.

Janez scanned n oranges; however, sometimes he decides to rescan one of the oranges (i-th orange) during the execution of your program. This means that from this scan on, he uses the updated value for the i-th orange.

Janez wants to analyse those oranges. He finds exclusive or (XOR) operation very interesting, so he decides to make some calculations. He selects a range of oranges from l to u (where lu) and wants to find out the value of XOR of all elements in that range, all pairs of consecutive elements in that range, all sequences 3 of consecutive elements and so on up to the sequence of u - l + 1consecutive elements (all elements in the range).

I.e. If l = 2 and u = 4 and there is an array of scanned values A, program should return the value of a2a3a4 ⊕ (a2a3) ⊕ (a3a4) ⊕ (a2a3a4), where ⊕ represents the XOR and ai represents the i-th element in array A.

Let XOR operation be defined as:

If the i-th bit of the first value is the same as the i-th bit of the second value, the i-th bit of the result is 0; If the i-th bit of the first value is different as the i-th bit of the second value, the i-th bit of the result is 1.

입력

In the first line of the input there are 2 positive integers n and q (total number of rescans and queries - actions).

In the next line, there are n space-separated non-negative integers, which represent values of the array A (scan results for oranges). Element ai contains the value for i-th orange. Index i starts with 1.

Actions are described in the next q lines with three space-separated positive integers.

If the action type is 1 (rescan), the first integer equals 1 and is followed by i (index of an orange that Janez wants to rescan) and j (the result of the rescan of the i-th orange).

If the action type is 2 (query), the first integer equals 2 and is followed by l and u.

출력

You should print exactly one integer for each query with the matching result for the query. You should print every value in a new line. Note that the i-th line of the output should match the result of the i-th query.

제한

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

서브태스크

번호배점제한
112

0 < n, q ≤ 100

218

0 < n, q ≤ 500 and there are no rescans (actions of type 1)

325

0 < n, q ≤ 5000

420

0 < n, q ≤ 2 · 105 and there are no rescans (actions of type 1)

525

No additional constraints.

예제 입력 1

3 3
1 2 3
2 1 3
1 1 3
2 1 3

예제 출력 1

2
0

At the beginning, A = [1, 2, 3]. The first query is on the full range. The result of the analysis is 1 ⊕ 2 ⊕ 3 ⊕ (1 ⊕ 2) ⊕ (2 ⊕ 3) ⊕ (1 ⊕ 2 ⊕ 3).

Then the value of the first orange is updated to 3. This leads to a change on the same query (on a range [1, 3]) 3 ⊕ 2 ⊕ 3 ⊕ (3 ⊕ 2) ⊕ (2 ⊕ 3) ⊕ (3 ⊕ 2 ⊕ 3) = 0.

예제 입력 2

5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4

예제 출력 2

2
5
4
4

채점 및 기타 정보

  • 예제는 채점하지 않는다.