Extreme XOR Sum
Imagine you have an array of n integers a = [a0, a1, a2, . . . , an−1]. To find the extreme sum of them you
have to do the following operations:
- Createanewlistt=[a0+a1,a1+a2,...,an−2+an−1].
- Leta=t.
- If a has only one element remaining, exit. Otherwise go to 1.
The last remaining element is the extreme sum for the given array. Extreme sum for a = [1, 2, 4] is 9.
To find the extreme XOR Sum, you have to do XOR operation instead of addition operation (in the step 1 above).
You are given an array of integers a. You have to answer q queries. Each query has the form of ‘b e’. You have to find the extreme XOR sum of the array [ab, ab+1, ab+2 . . . ae].
Input
The first line contains T (1 ≤ T ≤ 25). For each test case:
• The first line contains n (1 ≤ n ≤ 104).
• The second line contains n integers denoting the array a. Each element of the array will be an integer between 0 and 109.
• The third line contains q (1 ≤ q ≤ 30000).
• Eachofthenextqlinescontainstwointegersbande(0≤b≤e<n).
Output
For each test case, print the case number in the first line. In the next q lines, print a single line, the extreme XOR sum for the range [b, e] for the corresponding query.
Sample Input
1
5 14678 3
00
01
24
Sample Output
Case 1: 1
5
14