You're given an array A of N non-negative integers and Q queries. In each query, you're given two integers L and R (1≤L<R≤N). Find min(A[i]⊕A[j]) (L≤i<j≤R) for each query, where ⊕ is the bitwise XOR operator.
Input format
The first line contains two integers N and Q as described in the statement.
The second line contains N space-seperated integers denoting the elements of the array A.
Each of the following Q lines contain two integers L and R, as described in the statement.
Output format
The output must contain Q lines, where each line contains the answer for the corresponding query.
Constraints
1≤N,Q≤105
1≤A[i]≤210
In the first query, we can only choose i=1 and j=2, so the answer is 3 as a[1]⊕a[2]=1⊕2=3.
In the second query, we can choose i=2 and j=3, so the answer is 1.
