F. Максимизируйте разницу
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$b$$$ из $$$m$$$ целых неотрицательных чисел определим $$$f(b)$$$ как максимальное значение $$$\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)$$$ среди всех неотрицательных целых чисел $$$x$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.

Вам даны целые числа $$$n$$$ и $$$q$$$. Вы начинаете с пустого массива $$$a$$$. Выполните следующие $$$q$$$ запросов:

  • $$$v$$$: добавить $$$v$$$ в конец $$$a$$$ и вывести $$$f(a)$$$. Гарантируется, что $$$0 \leq v < n$$$.

Запросы даны в измененном виде.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 2^{22}$$$, $$$1 \leq q \leq 10^6$$$) — количество запросов.

Вторая строка каждого набора входных данных содержит $$$q$$$ разделенных пробелами целых чисел $$$e_1,e_2,\ldots,e_q$$$ ($$$0 \leq e_i < n$$$) — зашифрованные значения $$$v$$$.

Пусть $$$\mathrm{last}_i$$$ равно результату $$$(i-1)$$$-го запроса для $$$i\geq 2$$$ и $$$\mathrm{last}_i=0$$$ для $$$i=1$$$. Тогда значение $$$v$$$ для $$$i$$$-го запроса равно ($$$e_i + \mathrm{last}_i$$$) по модулю $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2^{22}$$$, а сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

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

В первом наборе входных данных в конце $$$a=[1,2]$$$. Для $$$i=1$$$ ответ всегда $$$0$$$, независимо от $$$x$$$. Для $$$i=2$$$ мы можем выбрать $$$x=5$$$.

Во втором наборе входных данных итоговое значение $$$a=[3,1,0,5]$$$.