E. Ива и Пав
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ива дала Паву массив $$$a$$$ из $$$n$$$ элементов.

Пусть $$$f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$$$ (здесь $$$\&$$$ обозначает побитовое И).

Обратите внимание, что $$$f(l, r)$$$ не определено, если $$$l>r$$$.

Ива также дала Паву $$$q$$$ запросов.

Каждый запрос состоит из 2 чисел, $$$k$$$ и $$$l$$$, и она хочет, чтобы Пав нашел наибольший индекс $$$r$$$ ($$$l \le r \le n$$$), такой что $$$f(l, r) \ge k$$$.

Пав хочет решить эту задачу быстро, потому что он не хочет расстроить Иву. Он нуждается в вашей помощи.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

Следующие $$$q$$$ строк каждого набора содержат по два числа, $$$l$$$ и $$$k$$$ ($$$1 \le l \le n$$$, $$$1 \le k \le 10^9$$$) — левая граница для отрезка и целое число $$$k$$$, описанное в условии.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$. Также гарантируется, что сумма $$$q$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите максимальный индекс $$$r$$$ ($$$l \le r \le n$$$) такой, что $$$a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ \ge \ k$$$.

Если такого $$$r$$$ не существует, выведите $$$-1$$$.

Пример
Входные данные
3
5
15 14 17 42 34
3
1 7
2 15
4 5
5
7 5 3 1 7
4
1 7
5 7
2 3
2 2
7
19 20 15 12 21 7 11
4
1 15
4 4
7 12
5 7
Выходные данные
2 -1 5 
1 5 2 2 
2 6 -1 5
Примечание

В первом наборе примера $$$n=5$$$, и массив $$$a = [15, 14, 17, 42, 34]$$$

Первый запрос просит найти наибольший индекс $$$r$$$, такой что $$$f(1, r) \ge 7$$$.

$$$f(1,1) = 15, \ f(1, 2) = 14, \ f(1,3)=0 \ f(1, 4)=0 \ f(1, 5)=0$$$, поэтому ответ $$$r=2$$$.

Второй запрос просит найти $$$f(2, r) \ge 15$$$. Поскольку такой $$$r$$$ не существует, ответ $$$-1$$$.

Третий запрос просит найти $$$f(4, r) \ge 5$$$. $$$f(4, 4) = 42, \ f(4, 5) = 34$$$, поэтому ответ $$$r=5$$$.

Во втором наборе примера $$$n=5$$$, и массив $$$a= [7, 5, 3, 1, 7]$$$.

Для первого запроса, $$$f(1, r) \ge 7$$$.

$$$f(1, 1)=7, \ f(1, 2)=5, \ f(1, 3) = 1, \ f(1,4) = 1, \ f(1, 5)=1$$$, поэтому ответ на этот запрос $$$1$$$.

Для второго запроса, $$$f(5, r) \ge 7$$$.

$$$f(5, 5) = 7$$$, поэтому ответ $$$5$$$.

Для третьего запроса, $$$f(2, r) \ge 3$$$.

$$$f(2, 2) = 5, \ f(2, 3) = 1, \ f(2, 4) = 1, \ f(2, 5) = 1$$$, поэтому ответ $$$2$$$.