In a quaint village, there lived a mathematician named Alice. One day, the villagers approached her with a unique challenge. They had an array \(A\) of size \(N\), that held the secrets of their village, and they needed answers to their questions. These questions came in the form of \(Q \) queries.
Each query was a request for enlightenment, presented with four mysterious numbers - \(L\), \(R\), \(X\), and \(Y\). For each query, Alice embarked on a journey through the array, focusing on the range from \(L\) to \(R\). She carefully counted how many times each number appeared in this range (from L to R).
With this newfound knowledge, she weaved a tapestry of wisdom in the form of a new array, \(B\). For every \(i\) from \(1\) to \(N\):
- \(B[i]\) = Bitwise XOR of all the numbers that occur exactly \(i\) times in the range \(L\) to \(R\) of array \(A\).
If none of the elements in the range from \(L\) to \(R\) occurred \(i\) times, she simply set \(B[i] = 0\).
Finally, Alice presented the villagers with the answer to their query, which was nothing short of a revelation. The answer for each query was the sum of the elements in her array \(B\), but only from position \(X\) to \(Y\), for the villagers believed that these specific positions held the key to their query's solution.
You now have to help Alice in completing this challenge.
Input format
- The first line contains a single integer \(T\), which denotes the number of test cases.
- For each test case:
- The first line contains \(N\) denoting the size of array \(A\).
- The second line contains \(N\) space-separated integers, denoting the elements of \(A\).
- The next line contains \(Q\) denoting the number of queries.
- The next \(Q\) lines contain 4 space-separated integers, denoting \(L\), \(R\), \(X\) and \(Y\).
Output format
For each test case, print the answer for each query in a new line.
Constraints
1 7 2 2 1 1 1 5 2 2 2 6 1 2 1 7 1 7
7 8
The first line denotes T = 1.
For test case \(1\):
- N = 7
- A = [2, 2, 1, 1, 1, 5, 2]
- Q = 2
Now,
- For the first query, we are given L=2, R=6, X=1, and Y=2.
- In range L(=2) to R(=6), elements 2 and 5 occur once, and element 1 occurs three times, so
- B[1] = 2 ⊕ 5, B[3] = 1, and all the remaining positions of array B will have 0.
- Array B is [7, 0, 1, 0, 0, 0, 0], and the sum of elements in range X(=1) to Y(=2) of array B is 7.
- Hence, the answer to the first query is 7.
- For the Second query, we are given L=1, R=7, X=1, and Y=7.
- In range L(=1) to R(=7), elements 1 and 2 occur three times, and element 5 occurs once, so
- B[1] = 5, B[3] = 1 ⊕ 2, and all the remaining positions of array B will have 0.
- Array B is [5, 0, 3, 0, 0, 0, 0], and the sum of elements in range X(=1) to Y(=7) of array B is 8.
- Hence, the answer to the second query is 8.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor