Background

In the epilogue, it will be described in detail why the “Land of Saki” can become the leader of the “Six Handsome Guys of Toaru Majutsu no Index”.

If you are wondering why the title does not include “Vento of the Front”, then you may want to check div.2.

But before that, you need to solve a construction problem.

Problem Description

You are given a natural number $n$ and a natural number parameter $k$. You need to construct a sequence $a$ of length $2^n$ such that every integer in $[0, 2^n)$ appears exactly once, and for all $i \in [2, 2^n]$, $\operatorname{popcount}(a_i \oplus a_{i-1}) = k$.
Here, $\operatorname{popcount}(x)$ denotes the number of $1$ bits in the binary representation of $x$, and $\oplus$ denotes the bitwise XOR operation.

If a solution exists, output 1 and print the sequence; otherwise, output 0.

Input Format

One line with two integers $n, k$, with the same meaning as in the statement.

Output Format

Output one integer 0 or 1 on the first line, where 0 means that no such sequence exists, and 1 means that such a sequence exists.
If the first line is 1, output $2^n$ integers on the next line, representing the sequence you construct. If there are multiple valid sequences, output any one.

4 3

1
0 14 3 13 6 8 5 11 12 2 15 1 10 4 9 7

4 2

0

Hint

This problem uses Special Judge and subtask-based evaluation.

For $100\%$ of the testdata, it is guaranteed that $1 \le n, k \le 20$.

Translated by ChatGPT 5