F1. XOR трансформации (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Разница между версиями состоит в том, что в этой версии ограничения на $$$n$$$ и $$$q$$$ меньше. Взломы можно делать только если вы решили все версии этой задачи.

Для массива $$$b$$$, состоящего из $$$m$$$ целых чисел, определим трансформацию следующим образом:

  • Выпишем значения $$$b_i\oplus b_j$$$ для всех $$$1\le i\lt j\le m$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ..
  • Возьмём $$$m$$$ наименьших среди выписанных значений.
  • Заменим элементы массива на взятые $$$m$$$ значений.

Например, рассмотрим трансформацию массива $$$[6, 7, 8, 9, 15]$$$. Мы выписываем значения $$$1, 1, 6, 7, 8, 9, 14, 14, 15, 15$$$. После трансформации массив становится $$$[1, 1, 6, 7, 8]$$$ — $$$5$$$ наименьших элементов.

Вам дан массив $$$a$$$, состоящий из $$$n$$$ неотрицательных целых чисел. Пусть $$$\max(a)$$$ обозначает максимальный элемент массива $$$a$$$, а $$$\min(a)$$$ — минимальный. Ваша задача — ответить на $$$q$$$ запросов, в каждом из которых вам даётся одно целое число $$$x$$$. Для каждого запроса найдите значение $$$\max(a) - \min(a)$$$ после $$$x$$$ трансформаций массива. Заметьте, что запросы независимы, то есть перед каждым запросом массив $$$a$$$ возвращается в исходное состояние.

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

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

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

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

Следующие $$$q$$$ строк каждого набора входных данных содержат по одному целому числу $$$x$$$ ($$$0\le x\lt 2^{30}$$$).

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

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел — ответ на каждый запрос.

Пример
Входные данные
4
5 1
0 0 1 1 1
1
5 2
6 7 8 9 15
0
1
8 2
102 92 15 19 25 54 62 36
2
1
10 1
56 73 81 23 17 92 50 34 67 78
2
Выходные данные
1
9
7
12
31
7
Примечание

В первом наборе входных данных после одной трансформации массив становится $$$[0, 0, 0, 0, 1]$$$. Здесь $$$\max(a) - \min(a) = 1 - 0 = 1$$$.

Во втором наборе входных данных массив равен $$$[6, 7, 8, 9, 15]$$$. Изначально $$$\max(a) - \min(a) = 15 - 6 = 9$$$. После трансформации массив становится $$$[1, 1, 6, 7, 8]$$$, где $$$\max(a) - \min(a) = 8 - 1 = 7$$$.