Codeforces Round 781 (Div. 2) |
---|
Finished |
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}$$$.
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$$$.
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}$$$.
256 1 3 2 141 22 32 42 540 2 1 107374182341 22 31 33 4
7 3 3 1 2 3 1 1073741823
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:
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:
Name |
---|