Static Range OR

Difficulty: 1600 5000 ms 128 MB

sparse-table

The array never changes. Answer Q queries: the bitwise OR of a_l..r.

Input: the first line has N and Q; the second line has the array; each of the next Q lines has l and r.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values| ≤ 10⁹

Sample Tests

5 2
3 1 4 1 5
1 3
2 5

7
5

1 1
-7
1 1

-7

Read the Editorial