XORanges

Janez loves oranges, so he built a scanner for oranges. With cameras and a Raspberry Pi 3b+ computer, he started creating 3D images of oranges. His image processor is not very good, so the only output he gets is a 32-bit integer that 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. Starting from 0, we can obtain D by adding 2i for every i-th bit that equals 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 (the i-th orange) while your program is running. This means that from that scan onward, he uses the updated value for the i-th orange.

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

That is, if l = 2 and u = 4 and there is an array of scanned values A, the program should return the value of a2 ⊕ a3 ⊕ a4 ⊕ (a2 ⊕ a3) ⊕ (a3 ⊕ a4) ⊕ (a2 ⊕ a3 ⊕ a4), where ⊕ represents XOR and ai represents the i-th element in array A.

Let the XOR operation be defined as follows.

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 from the i-th bit of the second value, the i-th bit of the result is 1.

The first line of the input contains 2 positive integers n and q (the total number of rescans and queries, that is, actions).

The next line contains n space-separated non-negative integers that represent the values of the array A (scan results for the oranges). Element ai holds the value for the i-th orange. Index i starts at 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 (the 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 on a new line. The i-th line of the output should match the result of the i-th query.

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