Interesting

The lady has posed an intriguing problem.

You are given an array a consisting of n 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 b.

An array c of size n is defined such that c[i] = min(a[i], b[i]).

The goal is to find the minimum possible value of c[1] ⊕ c[2] ⊕ ... ⊕ c[n].

The lady has m subarrays, and she wants to determine the answer for each one. Please assist her with this task!

Note that each of these m problems should be solved independently.

Input Format

The first line contains two integers n and m (1 ≤ n, m ≤ 150,000) — the number of elements in the array and the number of problems, respectively.

The second line contains n integers a[1], a[2], ..., a[n] (0 ≤ a[i] < 2^30) — the elements of the array.

Each of the following m lines contains two integers l and r (1 ≤ l ≤ r ≤ n), indicating that you need to solve the problem for the subarray [a[l], a[l+1], ..., a[r]].

Output Format

Output m integers — the answers to the problems.

Examples

Note

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 5 and 6 need to be swapped.

In the fourth problem, one possible solution is to swap the pairs (1, 3), (2, 6), and (4, 5).

The expression x ⊕ y refers to the bitwise XOR operation between the numbers x and y. This operation is available in all modern programming languages, for example, it is represented as "^" in C++ and Java, and as "xor" in Pascal.