Natalya Korshunova really misses Grigory Melekhov and wants to return to him. But, unfortunately, Grigory loves Aksinya, so Natalya decided to prove to her beloved that she is better than her.
To do this, Natalia went to Grigory and declared that she could solve any problem, whatever he suggested. Melekhov accepted the challenge.
Grigory gives Natalia an A array consisting of n non-negative integers. Then he asks her to perform q operations of the same type, consisting of the following: "Given the numbers l, r and k . Further, for each index i from l to r, the number k is substituted instead of the number A i and is considered a bitwise exclusive “or” all numbers in the segment \([l;r]\), after which the number Aith place again >i".
Thus, there are \(r – l + 1\) independent substitutions that do not change the array, and accordingly \(r – l + 1\) results in a bitwise exclusive “or”. Natalia needs to tell Grigory a bitwise exclusive “or” all substitution results (for a better understanding, check out the examples).
Help Natalia Korshunova cope with this task! Then Gregory will definitely return to her!
Input
The first line is an integer n (\(1 <= n <= 10^5\)) – number of array elements.
The second line contains n non-negative integers not exceeding \(10^8\).
The third line is an integer q (\(1 <= q <= 10^5\)) – number of requests.
The following contains q lines, each containing 3 integers: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
Output
You need to output
q responses for each query on one line separated by a space.
Examples
| # |
Input |
Output |
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
Explanation
First request:
1) 7 ⊕ 2⊕ 3 = 6
2) 1 ⊕ 7⊕ 3 = 5
3) 1 ⊕ 2⊕ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Answer: 7.
Second request:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Answer: 1.