D. Blackslex и цивилизация пингвинов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Для заданного целого числа $$$n$$$ рассмотрим перестановки$$$^{\text{∗}}$$$ $$$p$$$ массива $$$[0, 1, \ldots, 2^n - 1]$$$. Определим $$$$$$S(p) \;=\; \sum_{i=0}^{2^n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr),$$$$$$

где $$$\operatorname{popcount}(z)$$$ — это количество $$$1$$$-битов в двоичном представлении $$$z$$$ (например, $$$\operatorname{popcount}(5) = 2$$$, потому что $$$5 = 101_2$$$ имеет два $$$1$$$-бита в двоичном представлении), и $$$\&$$$ обозначает операцию побитового И. .

Перестановка считается священной, если она максимизирует $$$S(p)$$$. Найдите лексикографически минимальную$$$^{\text{†}}$$$ священную перестановку.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Массив $$$a$$$ лексикографически меньше массива $$$b$$$ такого же размера, если и только если выполняется следующее:

  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в массиве $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 16$$$) — количество наборов входных данных.

Каждый набор входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 16$$$).

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

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

Для каждого набора входных данных выведите $$$2^n$$$ целых числа $$$p_0, p_1, \ldots, p_{2^n-1}$$$ — требуемую перестановку.

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

Для первого набора входных данных существует две возможные перестановки.

  • $$$p = [0, 1]$$$, $$$S(p) = 0$$$
  • $$$p = [1, 0]$$$, $$$S(p) = 1$$$

Для второго набора входных данных $$$S([3, 1, 0, 2]) = 3$$$ является священной. Существуют и другие перестановки $$$p$$$, которые являются священными, такие как $$$p = [3, 2, 0, 1]$$$, но они не являются лексикографически минимальными.