MinimizOR

题意翻译

### 题目描述 给出一个长度为 $n$ 的非负整数数列 $a$，下标编号从 $1$ 到 $n$。 定义一个数列 $a$ 的代价为 $\min\limits_{i\neq j} a_i|a_j$，其中 $|$ 表示 [按位或](https://en.wikipedia.org/wiki/Bitwise_operation#OR) 运算。 $q$ 个询问，每个询问给出两个整数 $l,r\ (l<r)$，求数列 $a_l,a_{l+1},\dots,a_r$ 的最小代价。 ### 输入格式 每个测试点有多组数据。输入的第一行为一个整数 $t\ (1\leq t\leq 10^4)$ 表示数据组数。 每组数据的第一行为一个整数 $n\ (2\leq n\leq 10^5)$ 表示数列 $a$ 的长度。 第二行为 $n$ 个整数 $a_1,a_2,\dots,a_n\ (0\leq a_i< 2^{30})$。 第三行为一个整数 $q\ (1\leq q\leq 10^5)$ 表示询问个数。 下面 $q$ 行每行为两个整数 $l_j,r_j\ (1\leq l_j<r_j\leq n)$ 表示第 $j$ 个询问的 $l,r$。 每个测试点的数据保证 $\sum n,\sum q\leq 10^5$。 ### 输出格式 对于每个测试数据输出 $q$ 个整数，第 $j$ 个数表示数列 $a_{l_j},a_{l_j+1},\dots,a_{r_j}$ 的代价。

题目描述

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](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 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} $ .

输入输出样例

输入样例 #1

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

输出样例 #1

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