2507 - Xors on Segments - PK@Contest.bjtu

2507.Xors on Segments

Time Limit: 1s Memory Limit: 256MB

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 $2507_1.png$ . The function is defined for only u \le v.

For each query print the maximal value of the function f(ax,ay) over all lj \le x,y \le rj, ax \le ay.

Input Format(From the terminal/stdin)

The first line contains two integers n,m (1 \le n \le 5 \cdot 104, 1 \le m \le 5 \cdot 103) - the size of the array and the number of the queries.

The second line contains n integers ai (1 \le ai \le 106) - the elements of the array a.

Each of the next m lines contains two integers lj,rj (1 \le lj \le rj \le n) — the parameters of the j-th query.

Output Format(To the terminal/stdout)

For each query print the value aj on a separate line - the maximal value of the function f(ax,ay) over all lj \le x,y \le rj, ax \le ay.

Sample Input 1

Copy

6 3
1 2 3 4 5 6
1 6
2 5
3 4
 · \n
 · · · · · \n
 · \n
 · \n
 · \n

Sample Output 1

Copy

7
7
7
 \n
 \n
 \n

Sample Input 2

Copy

1 1
1
1 1
 · \n
 \n
 · \n

Sample Output 2

Copy

1
 \n

Sample Input 3

Copy

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
 ·  \n
  ·     ·    ·   · ·   \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

Sample Output 3

Copy

Submit

请先登录

Submit

题解(0)