MinimizOR
Contest: Codeforces Round 781 (Div. 2)
Difficulty rating: 2500
Tags: bitmasks, brute force, data structures, divide and conquer, greedy, implementation, two pointers

You are given an array $$$a$$$ of $$$n$$$ non-negative integers, numbered from $$$1$$$ to $$$n$$$.

Let's define the cost of the array $$$a$$$ as $$$\displaystyle \min_{i \neq j} a_i | a_j$$$, where $$$|$$$ denotes the bitwise OR operation.

There are $$$q$$$ queries. For each query you are given two integers $$$l$$$ and $$$r$$$ ($$$l < r$$$). For each query you should find the cost of the subarray $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.

Input format:
Each test case consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length array $$$a$$$.

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

The third line of each test case contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l_j$$$, $$$r_j$$$ ($$$1 \le l_j < r_j \le n$$$) — the description of the $$$j$$$-th query.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^5$$$.

Output format:
For each test case print $$$q$$$ numbers, where the $$$j$$$-th number is the cost of array $$$a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case the array $$$a$$$ is

$$$110_2, 001_2, 011_2, 010_2, 001_2$$$.

That's why the answers for the queries are:

- $$$[1; 2]$$$: $$$a_1 | a_2 = 110_2 | 001_2 = 111_2 = 7$$$;
- $$$[2; 3]$$$: $$$a_2 | a_3 = 001_2 | 011_2 = 011_2 = 3$$$;
- $$$[2; 4]$$$: $$$a_2 | a_3 = a_3 | a_4 = a_2 | a_4 = 011_2 = 3$$$;
- $$$[2; 5]$$$: $$$a_2 | a_5 = 001_2 = 1$$$.

In the second test case the array $$$a$$$ is

$$$00_2, 10_2, 01_2, \underbrace{11\ldots 1_2}_{30}$$$ ($$$a_4 = 2^{30} - 1$$$).

That's why the answers for the queries are:

- $$$[1; 2]$$$: $$$a_1 | a_2 = 10_2 = 2$$$;
- $$$[2; 3]$$$: $$$a_2 | a_3 = 11_2 = 3$$$;
- $$$[1; 3]$$$: $$$a_1 | a_3 = 01_2 = 1$$$;
- $$$[3; 4]$$$: $$$a_3 | a_4 = 01_2 | \underbrace{11\ldots 1_2}_{30} = 2^{30} - 1 = 1073741823$$$.

Example input:
2
5
6 1 3 2 1
4
1 2
2 3
2 4
2 5
4
0 2 1 1073741823
4
1 2
2 3
1 3
3 4

Example output:
7
3
3
1
2
3
1
1073741823

Editorial:
The key idea for the solution is that the answer always lies among no more than 31 minimal numbers. According to this idea, it is possible to build a segment tree for minimum on a segment. After that we only need to find no more than 31 minimums on the segment (each time we find one we change it to $$$\infty$$$) and, finally, we can find all $$$\text{OR}$$$s pairwise among these 31 numbers.
It is also possible to use the Merge Sort Tree and the same idea.
Now let's prove the key idea: let's prove by induction that if all numbers are less than $$$2^k$$$ then it's enough to consider $$$k + 1$$$ minimal numbers.
Base case: $$$k=1$$$, all numbers are from $$$0$$$ to $$$1$$$ and the proof is obvious.
Inductive step:
Let's show that for any $$$k \ge 1$$$ if for $$$k$$$ the statement is true then it's true for $$$k + 1$$$.
If all numbers have 1 in $$$k$$$-th bit then the $$$k$$$-th bit of the answer is also 1, that's why we only have to minimize the remaining bits. For these bits we can apply the induction hypothesis that $$$k + 1$$$ minimal numbers are enough. If at least two numbers have 0 in their $$$k$$$-th bit then the $$$k$$$-th bit in the answer is also 0. That's why we only consider only numbers with 0 in $$$k$$$-th bit and we have to minimize the remaining bits. Again applying the induction hypothesis, $$$k + 1$$$ minimal numbers are enough. If there is exactly one number with 0 in $$$k$$$-th bit then the $$$k$$$-th bit in the answer is 1 and we have to find $$$k + 1$$$ minimal numbers over $$$k$$$ bits. They are among $$$k + 2$$$ minimal numbers over $$$k + 1$$$ bits, so $$$k + 2$$$ minimal numbers are enough.