#P620F. Xors on Segments
-
ID: 3426
Type: RemoteJudge
10000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Xors on Segments
No submission language available for this problem.
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.
Samples
6 3
1 2 3 4 5 6
1 6
2 5
3 4
7
7
7
1 1
1
1 1
1
6 20
10 21312 2314 214 1 322
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 5
5 6
6 6
10
21313
21313
21313
21313
21313
21312
21313
21313
21313
21313
2314
2315
2315
214
215
323
1
323
322