Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

H. XOR и расстояния
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ различных элементов, и целое число $$$k$$$. Каждый элемент в массиве это неотрицательное целое число, не превосходящее $$$2^k-1$$$.

Обозначим через XOR расстояние для числа $$$x$$$ следующую величину:

$$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$

где через $$$\oplus$$$ обозначено побитовое исключающее ИЛИ.

Для каждого целого числа $$$x$$$ от $$$0$$$ до $$$2^k-1$$$ посчитайте $$$f(x)$$$.

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

Первая строка содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le 19$$$; $$$2 \le n \le 2^k$$$).

Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$).

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

Выведите $$$2^k$$$ чисел. $$$i$$$-е из них должно равняться $$$f(i-1)$$$.

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

Рассмотрим первый пример:

  • для $$$x = 0$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[6, 0, 3]$$$, и минимальный модуль разности между элементами равен $$$3$$$;
  • для $$$x = 1$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[7, 1, 2]$$$, и минимальный модуль разности между элементами равен $$$1$$$;
  • для $$$x = 2$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[4, 2, 1]$$$, и минимальный модуль разности между элементами равен $$$1$$$;
  • для $$$x = 3$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[5, 3, 0]$$$, и минимальный модуль разности между элементами равен $$$2$$$;
  • для $$$x = 4$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[2, 4, 7]$$$, и минимальный модуль разности между элементами равен $$$2$$$;
  • для $$$x = 5$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[3, 5, 6]$$$, и минимальный модуль разности между элементами равен $$$1$$$;
  • для $$$x = 6$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[0, 6, 5]$$$, и минимальный модуль разности между элементами равен $$$1$$$;
  • для $$$x = 7$$$, если мы применим XOR ко всем элементам массива с числом $$$x$$$, мы получим массив $$$[1, 7, 4]$$$, и минимальный модуль разности между элементами равен $$$3$$$.