Xors on Segments
Description
You are given an array with n integers ai and m queries. Each query is described by two integers (lj, rj).
Let's define the function 
. The function is defined for only u ≤ v.
For each query print the maximal value of the function f(ax, ay) over all lj ≤ x, y ≤ rj, ax ≤ ay.
The first line contains two integers n, m (1 ≤ n ≤ 5·104, 1 ≤ m ≤ 5·103) — the size of the array and the number of the queries.
The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.
Each of the next m lines contains two integers lj, rj (1 ≤ lj ≤ rj ≤ n) – the parameters of the j-th query.
For each query print the value aj on a separate line — the maximal value of the function f(ax, ay) over all lj ≤ x, y ≤ rj, ax ≤ ay.
Input
The first line contains two integers n, m (1 ≤ n ≤ 5·104, 1 ≤ m ≤ 5·103) — the size of the array and the number of the queries.
The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.
Each of the next m lines contains two integers lj, rj (1 ≤ lj ≤ rj ≤ n) – the parameters of the j-th query.
Output
For each query print the value aj on a separate line — the maximal value of the function f(ax, ay) over all lj ≤ x, y ≤ rj, ax ≤ ay.
6 3<br>1 2 3 4 5 6<br>1 6<br>2 5<br>3 4<br>
1 1<br>1<br>1 1<br>
6 20<br>10 21312 2314 214 1 322<br>1 1<br>1 2<br>1 3<br>1 4<br>1 5<br>1 6<br>2 2<br>2 3<br>2 4<br>2 5<br>2 6<br>3 4<br>3 5<br>3 6<br>4 4<br>4 5<br>4 6<br>5 5<br>5 6<br>6 6<br>
7<br>7<br>7<br>
1<br>
10<br>21313<br>21313<br>21313<br>21313<br>21313<br>21312<br>21313<br>21313<br>21313<br>21313<br>2314<br>2315<br>2315<br>214<br>215<br>323<br>1<br>323<br>322<br>