Zomato OA 2022 - The XOR Operation
You are given an array of integers A of size N. Now you are given Q queries to be performed over this array. In each of the queries, you are given 3 space-separated integers L, R, and X. You need to output the summation of the XOR of X with each of the array elements from the range L to R (both inclusive, using 1-based indexing).
The array does not change after any query.
Input Format:
- The first line contains the size of the array N and the number of queries Q.
- The second line contains N space-separated array elements.
- The next Q lines each contain 3 space-separated integers L, R, and X.
Output Format:
- Print Q lines, where the i-th line denotes the answer S_i to the i-th query.
Constraints:
- 1 ≤ N, Q ≤ 10^5
- 1 ≤ A[i] ≤ 10^9
Example
Input:
5 2
2 3 1 4 5
1 1 3
3 5 2
Output:
1
16
Explanation:
For the first query with L=1, R=1, and X=3:
- A[1] ⊕ X = 2 ⊕ 3 = 1
For the second query with L=3, R=5, and X=2:
- A[3] ⊕ X + A[4] ⊕ X + A[5] ⊕ X = 1 ⊕ 2 + 4 ⊕ 2 + 5 ⊕ 2 = 16.