Orange Scanner Analysis

Janez loves oranges! He built an orange scanner that outputs a 32‐bit integer for every scanned orange image. He scanned n oranges, but sometimes he rescans an orange, updating its 32‐bit integer. Janez is fascinated by the XOR operation. For analysis, he picks an interval from l to u (1-indexed) and wants to compute the XOR of the XOR sums of all contiguous subintervals contained in [l, u].

For example, if the sequence is denoted by \(a_1, a_2, \dots, a_n\) and for \(l=2, u=4\) the desired value is computed as:

[ 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), ]

Here, \(\oplus\) denotes the bitwise XOR operation with the following rules for bits \(x\) and \(y\):

\(x\)	\(y\)	\(x \oplus y\)
0	1	1
1	0	1
0	0	0
1	1	0

For example, \(13 \oplus 23 = 26\).

Observation: It can be shown that if the length of the interval \(m = u - l + 1\) is even then the answer is 0; if \(m\) is odd, then the answer equals the XOR of the elements at positions \(l, l+2, l+4, \dots\) within the interval.

You are given a sequence of oranges and need to support two types of operations:

• Q l u: Query the XOR value over all contiguous subintervals in the range [l, u].
• U i x: Update the i-th orange's integer to x (this represents a re-scan).

Input and Output: The input starts with an integer \(n\) representing the number of oranges. The second line contains \(n\) 32‐bit integers. The third line contains the number of operations \(q\). Each of the next \(q\) lines contains an operation in one of the two formats described above. For each query operation, output the result on a separate line.

inputFormat

The input is given as follows:

1. An integer \(n\) representing the number of oranges.
2. A line with \(n\) space-separated 32‐bit integers, the initial values for each orange.
3. An integer \(q\) representing the number of operations.
4. \(q\) lines, each representing an operation. Each operation is in one of the following formats:
   • Q l u — Query the XOR of the XOR sums of all contiguous subintervals in the range [\(l\), \(u\)].
   • U i x — Update the \(i\)-th orange's integer to \(x\).

Note: The indices are 1-indexed.

outputFormat

For each query operation, output a single line containing the answer.

sample

5
1 2 3 4 5
5
Q 1 5
U 3 10
Q 2 4
U 5 7
Q 1 5

7
6
12

</p>