[✗✓OI R1] 左方之地

题目背景

后记中将会详细描述帅神左方之地为何能成为「魔禁六帅」之首。 如果你很奇怪题目名称里面为什么没有前方之风,那你可能应该去看看 div.2。 但在此之前,你需要做一道构造题。

题目描述

给你一个自然数 $n$ 和一个自然数参数 $k$,你需要构造一个长度为 $2^n$ 的序列 $a$,满足 $[0,2^n)$ 间的所有整数恰好出现一次,并且 $\forall i\in[2,2^n]$,$\operatorname{popcount}(a_i \oplus a_{i-1})=k$。 其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数,$\oplus$ 表示[按位异或](https://oi-wiki.org/math/bit/#_1)运算。 若有解则输出 `1` 并输出这个序列,否则输出 `0`。

输入输出格式

输入格式


一行两个整数 $n,k$,意义同题目描述。

输出格式


第一行输出一个整数 `0` 或者 `1`,其中 `0` 代表不存在这样的序列,而 `1` 代表存在这样的序列。 如果第一行输出的是 `1`,接下来一行输出 $2^n$ 个整数,表示你构造的序列。如果有多个合法的序列,输出任意一个。

输入输出样例

输入样例 #1

4 3

输出样例 #1

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

输入样例 #2

4 2

输出样例 #2

0

说明

**本题采用 Special Judge,子任务评测**。 对于 $100\%$ 的数据,保证 $1\le n, k \le 20$。 | 子任务编号 | $n$ | $k$ | 子任务总分 |依赖子任务| | :--------: | :-----: | :-----: | :-------: | :-------: | | 0 | $\le 4$ | $\le 4$ | 5 || | 1 | $\le 8$ | $\le 8$ | 25 |Subtask 0| | 2 | | $=1$ | 10 || | 3 | | $=n-1$ | 15 || | 4 | | | 45 |Subtask 0~3| ![](https://cdn.luogu.com.cn/upload/image_hosting/lipqunc4.png)