Magical XOR Box

Xiao Wei owns a magical XOR box containing \( n \) elements. Each element has a weight \( v_i \). Whenever the mysterious incantation is recited, the box reveals the XOR sum of the weights of all its elements.

One day, Xiao Hai discovered the box and asked Xiao Wei: "Can I make \( q \) requests to the box? I wish to either change the weight of a particular element or add \( 1 \) to the weight of every element. And besides, I want to hear that mysterious incantation!" Xiao Wei agreed without hesitation.

You are now in charge of operating this magical XOR box. Fulfill all of Xiao Hai's requests!

inputFormat

The first line contains two integers \( n \) and \( q \) \( (1 \leq n, q \leq 10^5) \): the number of elements in the box and the number of queries.

The second line contains \( n \) integers \( v_1, v_2, \ldots, v_n \) \( (0 \leq v_i \leq 10^9) \) representing the initial weights.

Each of the following \( q \) lines represents a query. A query can be one of the following three types:

• 1 i x: Change the weight of the \( i \)-th element to \( x \) (1-indexed; \( 0 \leq x \leq 10^9 \)).
• 2: Add \( 1 \) to the weight of every element.
• 3: Output the XOR sum of all the elements in the box.

It is guaranteed that there is at least one query of type 3.

outputFormat

For each query of type 3, output the XOR sum of all elements in the box on a separate line.

sample

3 5
1 2 3
3
2
3
1 2 5
3

0
5
3