E. МинимизатOR
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$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}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$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 < 2^{30}$$$) — элементы массива $$$a$$$.

Третья строка каждого набора входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j < r_j \le n$$$) — описание $$$j$$$-го запроса.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ чисел, где $$$j$$$-е число равно стоимости массива $$$a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных массив $$$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$$$.