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

В ряд расположено $$$n$$$ слаймов, $$$i$$$-й из которых имеет вес $$$w_i$$$. Слайм $$$i$$$ может съесть другого слайма $$$j$$$, если $$$w_i \geq w_j$$$; после этого слайм $$$j$$$ исчезает, а вес слайма $$$i$$$ становится равен $$$w_i \oplus w_j$$$$$$^{\text{∗}}$$$.

Король слаймов хочет провести эксперимент с параметром $$$x$$$ следующим образом:

  • Добавить новый слайм с весом $$$x$$$ в правый конец ряда (после $$$n$$$-го слайма).
  • Этот новый слайм съедает слайм слева от него, если он может это сделать, и затем занимает его место (перемещается на одно место влево). Он будет продолжать это делать, пока слева от него не останется слаймов или вес слайма слева больше его собственного веса. (Другие слаймы не съедаются в процессе.)
  • Счёт эксперимента — это количество съеденных слаймов.

Король слаймов собирается задать вам $$$q$$$ запросов. В каждом запросе вам будет дано целое число $$$x$$$, и вам нужно определить счёт эксперимента с параметром $$$x$$$.

Обратите внимание, что король не хочет, чтобы вы на самом деле проводили каждый эксперимент; его слаймы бы погибли, что не очень хорошо. Он только спрашивает, чему гипотетически равен счёт такого эксперимента; другими словами, запросы не персистентны.

$$$^{\text{∗}}$$$Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

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

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

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

Следующая строка содержит $$$n$$$ целых чисел $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i < 2^{30}$$$) — веса слаймов.

Следующие $$$q$$$ строк содержат по одному целому числу $$$x$$$ ($$$ 1 \le x < 2^{30}$$$) — параметр для эксперимента.

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

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

Для каждого запроса выведите одно целое число — счёт эксперимента.

Пример
Входные данные
3
1 1
5
6
4 4
1 5 4 11
8
13
16
15
10 9
10 4 3 9 7 4 6 1 9 4
2
6
5
6
9
8
6
2
7
Выходные данные
1
0 2 4 2
0 1 1 1 3 3 1 0 1
Примечание

Для первого запроса второго набора входных данных:

  • Слайм весом $$$8$$$ будет добавлен в конец, после чего $$$w = [1, 5, 4, 11, \color{red}8]$$$.
  • Добавленный слайм имеет меньший вес, чем слайм слева от него, поэтому он не может его съесть, и, таким образом, процесс заканчивается после того, как не было съедено ни одного слайма. Счёт эксперимента равен $$$0$$$.
Для второго запроса второго набора входных данных:
  • Слайм весом $$$13$$$ будет добавлен в конец, так что $$$w = [1, 5, 4, 11, \color{red}{13}]$$$.
  • Добавленный слайм имеет больший вес, чем слайм слева от него, и поэтому он его съест. Его вес станет $$$13 \oplus 11 = 6$$$. Теперь $$$w = [1, 5, 4, \color{red}{6}]$$$.
  • Добавленный слайм теперь съест слайм слева от него, и его вес станет $$$6 \oplus 4 = 2$$$. Теперь $$$w = [1, 5, \color{red}{2}]$$$.
  • Добавленный слайм больше не может съесть слайм слева от него, поэтому процесс заканчивается со счётом $$$2$$$.