Fixed Hamming Distance Gray Code

Given two natural numbers \(n\) and \(k\), construct a sequence \(a_0,a_1,\ldots,a_{2^n-1}\) consisting of all integers in \([0,2^n)\) (each integer appears exactly once), such that for every index \(i\) with \(1 \le i < 2^n\), the following condition holds:

[ \operatorname{popcount}(a_i \oplus a_{i-1}) = k, ]

Here, \(\operatorname{popcount}(x)\) counts the number of \(1\)'s in the binary representation of \(x\), and \(\oplus\) denotes the bitwise XOR operation.

If such a sequence exists, output 1 in the first line, and in the second line print the sequence (numbers separated by a single space). Otherwise, output 0.

Note: It can be shown that a necessary condition for the existence of such a sequence is that \(k\) is odd and \(1 \le k \le n\). For example, when \(k=1\), a standard Gray code is a valid sequence.

inputFormat

The input contains two natural numbers \(n\) and \(k\) separated by spaces. Here, \(n\) represents the number of bits (hence the sequence length is \(2^n\)), and \(k\) is the required Hamming distance between consecutive elements as defined by the formula:

[ \operatorname{popcount}(a_i \oplus a_{i-1}) = k. ]

outputFormat

If a valid sequence exists, print 1 in the first line followed by a line containing the \(2^n\) sequence elements (separated by a single space). If no valid sequence exists, output only 0.

sample

3 1

1
0 1 3 2 6 7 5 4