Xors on Segments

ID: 27726

远端评测题

10000ms

512MiB

难度: 10

上传者:

标签>

data structures

strings

trees

*2800

Description

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.

The first line contains two integers n, m (1 ≤ n ≤ 5·10⁴, 1 ≤ m ≤ 5·10³) — the size of the array and the number of the queries.

The second line contains n integers a_i (1 ≤ a_i ≤ 10⁶) — 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.

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.

The first line contains two integers n, m (1 ≤ n ≤ 5·10⁴, 1 ≤ m ≤ 5·10³) — the size of the array and the number of the queries.

The second line contains n integers a_i (1 ≤ a_i ≤ 10⁶) — 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.

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.

6 3
1 2 3 4 5 6
1 6
2 5
3 4

7
7
7

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