L. OR + AND
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For an array $$$a$$$, define $$$f(a)$$$ as follows:

  • First, partition $$$a$$$ into two disjoint subsets $$$S_1$$$ and $$$S_2$$$ (could be empty), where each element belongs to exactly one subset.
  • Calculate the bitwise OR of all elements in $$$S_1$$$. Let it be $$$v_1$$$. Particularly, $$$v_1 = 0$$$ if $$$S_1 = \emptyset$$$.
  • Calculate the bitwise AND of all elements in $$$S_2$$$. Let it be $$$v_2$$$. Particularly, $$$v_2 = 0$$$ if $$$S_2 = \emptyset$$$.
  • The score of this partition is $$$v_1+v_2$$$.
  • $$$f(a)$$$ is defined as the maximum score over all possible partitions.

You are given an array $$$a$$$ of length $$$n$$$. Answer $$$q$$$ queries in the following form:

  • $$$l~r$$$ ($$$1 \le l \le r \le n$$$): compute $$$f([a_l,a_{l+1},\ldots,a_r])$$$.
Input

The first line of each test contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^6$$$) — the length of $$$a$$$ and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 2^{30}$$$) — the elements of $$$a$$$.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), describing a query.

Output

For each query, output $$$f([a_l,a_{l+1},\ldots,a_r])$$$.

Example
Input
6 3
5 4 2 1 1 8
1 3
1 6
2 5
Output
11
20
8