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:

1. Createanewlistt=[a0+a1,a1+a2,...,an−2+an−1].
2. Leta=t.
3. 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