Problem Description

Janez likes oranges. He built an orange scanner, but for each scanned orange, the image output can only be a $32$-bit integer.

He scanned a total of $n$ oranges, but sometimes he rescans an orange, causing the $32$-bit integer of that orange to be updated.

Janez wants to analyze these oranges. He finds the XOR operation very interesting. Each time he chooses an interval from $l$ to $u$, and he wants to get the XOR of the XOR sums of all subintervals within this interval.

For example, when $l=2,u=4$, let the integer of the $i$-th orange in the orange sequence $A$ be $a_i$. Then what he asks for is:

$$a_2 \oplus a_3 \oplus a_4 \oplus (a_2\oplus a_3)\oplus(a_3\oplus a_4)\oplus(a_2\oplus a_3 \oplus a_4)$$

---

Note: $\oplus$ in the expression represents the bitwise XOR operation. The XOR rules are as follows.

For the $i$-th bit of two numbers, denoted by $x,y$, we have:

$x$	$y$	$x\oplus y$
$0$	$1$	$1$
$1$	$0$
$0$		$0$
$1$

Example: $13\oplus 23=26$

$13=$	$0\cdots 001101$
$23=$	$0\cdots 010111$
$13\oplus 23=$	$0\cdots 011010$

Input Format

The first line contains two positive integers $n,q$, representing the number of oranges and the number of operations.

The next line contains $n$ non-negative integers, representing the value obtained by scanning each orange, indexed starting from $1$.

The next $q$ lines each contain three numbers:

• If the first number is $1$, then a positive integer $i$ and a non-negative integer $j$ follow, meaning to modify the scanned value $a_i$ of the $i$-th orange to $j$.

• If the first number is $2$, then two positive integers $u,l$ follow, meaning to query the answer for this interval.

Output Format

For each query, output one non-negative integer per line, representing the required total XOR sum.

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

2
0

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
5
4
4

Hint

Explanation of Sample Input/Output 1

• Initially, $A=[1,2,3]$, and the query result is $1\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=2$.

• After the modification, the first position is changed to $3$, and the query result is $3\oplus 2\oplus 3\oplus(3\oplus 2)\oplus (2\oplus 3)\oplus(3\oplus 2\oplus 3)=0$.

---

Constraints

This problem uses bundled testdata with a total of 5 subtasks.

• Subtask 1 (12 points): $1\le n,q\le 10^2$, no special restrictions.
• Subtask 2 (18 points): $1\le n,q\le 5\times 10^2$, and there are no update operations.
• Subtask 3 (25 points): $1\le n,q\le 5\times 10^3$, no special restrictions.
• Subtask 4 (20 points): $1\le n,q\le 2\times 10^5$, and there are no update operations.
• Subtask 5 (25 points): $1\le n,q\le 2\times 10^5$, no special restrictions.

For all testdata, $0\le a_i\le 10^9,1\le n,q\le 2\times 10^5$.

---

Notes

Original problem: eJOI2019 Problem A. XORanges

Statement and data source: LibreOJ

Translated by ChatGPT 5