# Xors on Segments

You are given an array with n integers a i and m queries. Each query is described by two integers (l j, r j).

Let’s define the function . The function is defined for only u ≤ v.

For each query print the maximal value of the function f(a x, a y) over all l j ≤ x, y ≤ r j,  a x ≤ a y.

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 a i (1 ≤ a i ≤ 106) — the elements of the array a.

Each of the next m lines contains two integers l j, r j (1 ≤ l j ≤ r j ≤ n) – the parameters of the j-th query.

Output

For each query print the value a j on a separate line — the maximal value of the function f(a x, a y) over all l j ≤ x, y ≤ r j,  a x ≤ a y.

Examples

input

6 31 2 3 4 5 61 62 53 4

output

777

input

1 111 1

output

1

input

6 2010 21312 2314 214 1 3221 11 21 31 41 51 62 22 32 42 52 63 43 53 64 44 54 65 55 66 6

output

10213132131321313213132131321312213132131321313213132314231523152142153231323322

Solution:

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000010;

int z[MAX];

const int N = 50010;

int a[N], g[N], b[N];
int from[N], to[N], best[N];

int main() {
z[0] = 0;
for (int i = 1; i < MAX; i++) {
z[i] = z[i - 1] ^ i;
}
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
g[i] = z[a[i]];
}
for (int i = 0; i < m; i++) {
scanf("%d %d", from + i, to + i);
from[i]--; to[i]--;
best[i] = -1;
}
for (int i = 0; i < n; i++) {
int mx = 0;
for (int j = i; j < n; j++) {
int cur = g[i] ^ g[j] ^ (a[i] < a[j] ? a[i] : a[j]);
mx = max(mx, cur);
b[j] = mx;
}
for (int k = 0; k < m; k++) {
if (from[k] <= i && i <= to[k]) {
best[k] = max(best[k], b[to[k]]);
}
}
}
for (int k = 0; k < m; k++) {
printf("%d\n", best[k]);
}
return 0;
}