C. Бинарное вино
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ в диапазоне $$$[0,2^{30})$$$.

Вы можете потратить $$$1$$$ монету, чтобы увеличить любое $$$a_i$$$ на $$$1$$$. Вы можете выполнять эту операцию любое количество раз.

Вам нужно решить $$$q$$$ запросов; для каждого запроса вам дано целое число $$$c$$$, также в диапазоне $$$[0,2^{30})$$$. Вам хотелось бы, чтобы существовала последовательность $$$b$$$ длиной $$$n$$$ со следующими свойствами:

Пожалуйста, вычислите минимальное количество монет, которое вам придется потратить, чтобы существовала подходящая $$$b$$$.

Запросы являются независимыми, что означает, что любые операции, которые вы выполняете над последовательностью $$$a$$$, не повлияют на будущие запросы.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i \lt 2^{30}$$$) — начальная последовательность $$$a$$$.

Каждая из следующих $$$q$$$ строк содержит одно целое число $$$c$$$ ($$$0\le c \lt 2^{30}$$$) — целевой XOR.

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

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$5\cdot10^4$$$.

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

Для каждого запроса выведите одно целое число — минимальное количество монет, которое вам придется потратить, чтобы существовала подходящая $$$b$$$.

Пример
Входные данные
4
2 1
5 7
9
3 1
9 9 8
24
6 4
1 1 4 5 1 4
10
20
30
40
1 1
0
0
Выходные данные
1
7
3
11
16
31
0
Примечание

В первом наборе входных данных мы тратим $$$1$$$ монету, чтобы увеличить $$$a_2$$$ на $$$1$$$, в результате чего получаем последовательность $$$[5,8]$$$. Подходящая $$$b$$$ будет $$$[1,8]$$$. Можно показать, что нельзя потратить меньше $$$1$$$ монеты для достижения цели.

Во втором наборе входных данных мы можем потратить $$$7$$$ монет, чтобы увеличить $$$a_1$$$ на $$$7$$$, в результате чего получаем последовательность $$$[16,9,8]$$$. Подходящая $$$b$$$ будет $$$[16,9,1]$$$.