Read problems statements in Mandarin chinese, Russian and Vietnamese as well.

You are given a sequence A_{1}, A_{2}, ..., A_{N} and Q queries. In each query, you are given two parameters L and R; you have to find the smallest integer X such that 0 ≤ X < 2^{31} and the value of (A_{L} xor X) + (A_{L+1} xor X) + ... + (A_{R} xor X) is maximum possible.

Note: xor denotes the bitwise xor operation.

------ Input ------

The first line of the input contains two space-separated integers N and Q denoting the number of elements in A and the number of queries respectively.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}.
Each of the next Q lines contains two space-separated integers L and R describing one query.

------ Output ------

For each query, print a single line containing one integer — the minimum value of X.

------ Constraints ------

$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$0 ≤ A_{i} < 2^{31} for each valid i$

------ Subtasks ------

Subtask #1 (18 points):

$1 ≤ N ≤ 10^{3}$
$1 ≤ Q ≤ 10^{3}$
$0 ≤ A_{i} < 2^{10} for each valid i$

Subtask #2 (82 points): original constraints

----- Sample Input 1 ------
5 3

20 11 18 2 13

1 3

3 5

2 4
----- Sample Output 1 ------
2147483629

2147483645

2147483645

见题面

见题面