Дан массив \(a\) из \(n\) неотрицательных целых чисел, пронумерованных от \(1\) до \(n\).
Назовём стоимостью массива \(a\) величину, равную \(\displaystyle \min_{i \neq j} a_i | a_j\), где \(|\) обозначает операцию побитового ИЛИ.
Есть \(q\) запросов. Каждый запрос состоит из двух чисел \(l\) и \(r\) (\(l < r\)). Для каждого запроса необходимо вывести стоимость массива \(a_{l}, a_{l + 1}, \ldots, a_{r}\).
Выходные данные
Для каждого набора входных данных выведите \(q\) чисел, где \(j\)-е число равно стоимости массива \(a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}\).
Примечание
В первом наборе входных данных массив \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
7
3
3
1
2
3
1
1073741823
|