CF1665E.MinimizOR

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 \lt r$). For each query you should find the cost of the subarray $a_{l}, a_{l + 1}, \ldots, a_{r}$.

给你一个长度为 $n$ 的非负整数数组 $a$，元素编号从 $1$ 到 $n$。

我们定义数组 $a$ 的代价为 $\displaystyle \min_{i \neq j} a_i | a_j$，其中 $|$ 表示按位或运算。

共有 $q$ 个查询。对于每个查询，你将得到两个整数 $l$ 和 $r$（满足 $l \lt r$）。对每个查询，你需要求出子数组 $a_{l}, a_{l + 1}, \ldots, a_{r}$ 的代价。

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 \lt 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 \lt 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$.

每个测试用例包含若干个测试案例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试案例的数量。

每个测试案例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 数组 $a$ 的长度。

每个测试案例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \lt 2^{30}$）—— 数组 $a$ 的元素。

每个测试案例的第三行包含一个整数 $q$（$1 \le q \le 10^5$）—— 查询的数量。

接下来的 $q$ 行中，每行包含两个整数 $l_j$、$r_j$（$1 \le l_j \lt r_j \le n$）—— 第 $j$ 个查询的描述。

保证所有测试案例中 $n$ 的总和与 $q$ 的总和均不超过 $10^5$。

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}$.

对每个测试用例，输出 $q$ 个数字，其中第 $j$ 个数字是数组 $a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$ 的代价。

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$.

第一个测试用例中，数组 $a$ 为

$110_2, 001_2, 011_2, 010_2, 001_2$。

因此各查询的答案为：

• $[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$。

第二个测试用例中，数组 $a$ 为

$00_2, 10_2, 01_2, \underbrace{11\ldots 1_2}_{30}$（即 $a_4 = 2^{30} - 1$）。

因此各查询的答案为：

• $[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$。