F. Личность босса
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время расследования происхождения Диаволо, Джорно получает от Полнареффа секретный код. Код можно представить в виде бесконечной последовательности целых положительных чисел: $$$a_1, a_2, \dots $$$. Джорно сразу видит закономерность, лежащую в основе кода. Первые $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ являются известными. Для $$$i > n$$$ значение $$$a_i$$$ равно $$$(a_{i-n}\ |\ a_{i-n+1})$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.

Части информации о Диаволо скрыты в $$$q$$$ вопросах. Каждый вопрос связан с положительным целым числом $$$v$$$, а ответом на него является наименьший индекс $$$i$$$, такой, что $$$a_i > v$$$. Если такого $$$i$$$ не существует, то ответом будет $$$-1$$$. Помогите Джорно ответить на вопросы!

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10\,000$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$ , $$$1 \leq q \leq 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — части кода, которые определяют шаблон.

В $$$i$$$-й из следующих $$$q$$$ строк содержится одно целое число $$$v_i$$$ ($$$0 \leq v_i \leq 10^9$$$) — вопрос, который задает Джорно.

Сумма $$$n$$$ и $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Выведите $$$q$$$ чисел. Число $$$i$$$ является ответом на $$$i$$$-й вопрос, заданный Джорно.

Пример
Входные данные
3
2 3
2 1
1
2
3
4 5
0 2 1 3
0
1
2
3
4
5 5
1 2 3 4 5
7
2
6
0
4
Выходные данные
1
3
-1
2
2
4
-1
-1
-1
3
8
1
5
Примечание

В первом примере $$$a = [2,1,3,3,\ldots]$$$.

  • Для первого вопроса, $$$a_1=2$$$ – элемент с наименьшим индексом, больший чем $$$1$$$.
  • Для второго вопроса, $$$a_3=3$$$ – элемент с наименьшим индексом, больший чем $$$2$$$.
  • Для третьего вопроса, нет индекса $$$i$$$, такого что $$$a_i > 3$$$.
.