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

Побитовый nor$$$^{\text{∗}}$$$ массива $$$k$$$-битных целых чисел $$$b_1, b_2, \ldots, b_m$$$ можно вычислить, рассчитывая побитовый nor кумулятивно слева направо. Более формально, $$$\operatorname{nor}(b_1, b_2, \ldots, b_m) = \operatorname{nor}(\operatorname{nor}(b_1, b_2, \ldots, b_{m - 1}), b_m)$$$ для $$$m\ge 2$$$, и $$$\operatorname{nor}(b_1) = b_1$$$.

Вам дан массив $$$k$$$-битных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Для каждого индекса $$$i$$$ ($$$1\le i\le n$$$) найдите максимальный побитовый nor среди всех подмассивов$$$^{\text{†}}$$$ массива $$$a$$$, содержащих индекс $$$i$$$. Другими словами, для каждого индекса $$$i$$$ найдите максимальное значение $$$\operatorname{nor}(a_l, a_{l+1}, \ldots, a_r)$$$ среди всех $$$1 \le l \le i \le r \le n$$$.

$$$^{\text{∗}}$$$ Логический nor двух булевых значений равен $$$1$$$, если оба значения равны $$$0$$$, и $$$0$$$ в противном случае. Побитовый nor двух $$$k$$$-битных целых чисел вычисляется путем выполнения логической операции nor для каждой пары соответствующих битов.

Например, давайте вычислим $$$\operatorname{nor}(2, 6)$$$, когда они представлены как $$$4$$$-битные числа. В двоичном виде $$$2$$$=$$$0010_2$$$ и $$$6=0110_2$$$. Следовательно, $$$\operatorname{nor}(2,6) = 1001_2 = 9$$$, так как при выполнении логических операций nor слева направо, мы имеем:

  • $$$\operatorname{nor}(0,0) = 1$$$
  • $$$\operatorname{nor}(0,1) = 0$$$
  • $$$\operatorname{nor}(1,0) = 0$$$
  • $$$\operatorname{nor}(1,1) = 0$$$

Обратите внимание, что если бы $$$2$$$ и $$$6$$$ были представлены как $$$3$$$-битные целые числа, то $$$\operatorname{nor}(2,6) = 1$$$.

$$$^{\text{†}}$$$Массив $$$x$$$ является подмассивом массива $$$y$$$, если $$$x$$$ может быть получен из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 17$$$) — количество элементов в массиве и количество битов элементов массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2^k - 1$$$) — элементы массива $$$a$$$.

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

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

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

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

В первом наборе входных данных подмассивы, которые содержат индекс $$$1$$$, это $$$[1]$$$ и $$$[1, 3]$$$. Значения их побитового nor равны $$$1$$$ и $$$0$$$ соответственно. Следовательно, ответ для индекса $$$1$$$ равен $$$1$$$. Подмассивы, которые содержат индекс $$$2$$$, это $$$[3]$$$ и $$$[1, 3]$$$. Значения их побитового nor равны $$$3$$$ и $$$0$$$ соответственно. Следовательно, ответ для индекса $$$2$$$ равен $$$3$$$.

Во втором наборе входных данных:

  • Для $$$i = 1$$$ подмассив с максимальным побитовым nor это $$$[a_1, a_2, a_3, a_4, a_5] = [1, 7, 4, 6, 2]$$$, $$$\operatorname{nor}(1, 7, 4, 6, 2) = 5$$$
  • Для $$$i = 2$$$ подмассив с максимальным побитовым nor это $$$[a_2] = [7]$$$, $$$\operatorname{nor}(7) = 7$$$
  • Для $$$i = 3$$$ подмассив с максимальным побитовым nor это $$$[a_1, a_2, a_3, a_4, a_5] = [1, 7, 4, 6, 2]$$$, $$$\operatorname{nor}(1, 7, 4, 6, 2) = 5$$$
  • Для $$$i = 4$$$ подмассив с максимальным побитовым nor это $$$[a_4] = [6]$$$, $$$\operatorname{nor}(6) = 6$$$
  • Для $$$i = 5$$$ подмассив с максимальным побитовым nor это $$$[a_1, a_2, a_3, a_4, a_5] = [1, 7, 4, 6, 2]$$$, $$$\operatorname{nor}(1, 7, 4, 6, 2) = 5$$$