Zomato OA-3 2022

Problem Description

You are given an array A of integers with size N. Additionally, there are Q queries to be processed on this array. For each query, three integers L, R, and X are provided, and the task is to compute the sum of the XOR between X and each element in the subarray from index L to R (inclusive, based on 1-based indexing).

Note: The array remains unchanged throughout all the queries.

Input Format:

• The first line contains two integers: the size of the array N and the number of queries Q.
• The second line consists of N space-separated integers, representing the array elements.
• The next Q lines each contain three space-separated integers L, R, and X, describing each query.

Output Format:

Print Q lines, where the i-th line represents the result of 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.