小 T 有一个 n+1 层的满二叉树 T。具体来说,这棵树以 1 为根,共有 2n+1−1 个结点。对于每个点 x (1≤x<2n),它的左儿子和右儿子分别为 2x 和 2x+1。
有一天,树 T 上每两个相邻的叶子 y 和 y+1 (2n≤y≤2n+1−2) 之间都连了一条边。小 T 对它非常失望,因为它不再是一棵真正的树了。小 T 想到他刚刚学过图论中的缩点,于是他决定应用自己的知识来让它重新变成一棵树。
具体来说,小 T 首先需要决定他所用的颜色数 m,接着他要给每个点 i 染上一种颜色 ci (1≤ci≤m)。之后建立一张 m 个点的新图 G,G 中两点 i,j (i≠j) 有边当且仅当 T 中存在两个相连的点 u,v 满足 cu=i, cv=j。小 T 要求图 G 必须是一棵树。
为了更加美观,小 T 希望每种颜色至少有 1 个点使用,且至多有 k 个点使用。你能否帮助他构造出想要的方案呢?
输入格式
一行两个数 n,k,分别表示满二叉树层数和每种颜色的数量限制。
输出格式
第一行一个数 m 表示使用的颜色数。
第二行 2n+1−1 个数,其中第 i 个数表示 i 号点染成的颜色 ci。
样例输入 1
1 12
样例输出 1
2 2 2 1
样例输入 2
2 12
样例输出 2
3 2 3 2 1 3 2 3
样例解释
样例 1 中图 G 有 2 个点,有 1 条边 (1,2),边 (1,2) 对应 T 的边 (1,3),(2,3)。
样例 2 中图 G 有 3 个点,有 2 条边 (1,3),(3,2),边 (1,3) 对应 T 的边 (4,2),(4,5),边 (3,2) 对应 T 的边 (2,1),(5,6),(3,7),(6,7)。
数据范围
对于所有数据,1≤n≤20,12≤k≤1.1×106。
子任务 1(11 分):n≤4,k=12。
子任务 2(8 分):k=1.1×106。
子任务 3(15 分):k=6×105。
子任务 4(16 分):k=5000。
子任务 5(15 分):k=200。
子任务 6(35 分):k=12。