Task
You became fond of the problem Interval XOR from the third round, so we decided to give you a more challenging version.
You are given an array of length , which has positive integers, and queries.
For each query, we will give the values and and we are required to solve the problem Interval XOR for the values in the range [] in the array. In other words, you will need to find the maximum XOR we can get by removing exactly one value from that interval.
Input
The first line of the input will contain and (), the number of values in the array and the number of query operations your program will have to perform.
The next line of the array will have values, the starting values of the array ().
The next lines of the array will contain values each, respecting the format given earlier in the statement ().
For tests worth points, .
For tests worth more points, for all the queries.
Output
The output will contain a line for each operation given in the input.
Example 1
stdin
5 4
4 5 2 6 7
1 4
1 3
3 5
1 5
stdout
7
7
5
7