Interesting#9096
The lady has posed an intriguing problem.
You are given an array consisting of non-negative numbers.
You are allowed to swap pairs of elements in the array, but each element's position can be altered at most once. After making these swaps, you will obtain a new array .
An array of size is defined such that c_i = \min(a_i, b_i).
The goal is to find the minimum possible value of c_1 \oplus c_2 \oplus \ldots \oplus c_n.
The lady has subarrays, and she wants to determine the answer for each one. Please assist her with this task!
Note that each of these problems should be solved independently.
The first line contains two integers and (1 \leq n, m \leq 150\ 000) — the number of elements in the array and the number of problems, respectively.
The second line contains integers a_1, a_2, \ldots, a_n (0 \leq a_i < 2^{30}) — the elements of the array.
Each of the following lines contains two integers and (1 \leq l \leq r \leq n), indicating that you need to solve the problem for the subarray [a_l, a_{l+1}, \ldots, a_r].
Output integers — the answers to the problems.
Example 1
In the first problem, it is not possible to swap elements of the subarray.
In the second problem, achieving the optimal result does not require swapping elements of the subarray.
In the third problem, to achieve the optimal result, elements and need to be swapped.
In the fourth problem, one possible solution is to swap the pairs (), (), and ().
_________________________________________ The expression x \oplus y refers to the bitwise XOR operation between the numbers and . This operation is available in all modern programming languages, for example, it is represented as "'^'" in C++ and Java, and as "xor" in Pascal.