Little T has a full binary tree $T$ with $n+1$ levels. Specifically, the tree is rooted at $1$ and has a total of $2^{n+1}-1$ nodes. For each node $x$ $(1\leq x < 2^n)$, its left child is $2x$ and its right child is $2x+1$.

One day, an edge was added between every two adjacent leaves $y$ and $y+1$ $(2^n\leq y\leq 2^{n+1}-2)$ in the tree $T$. Little T was very disappointed because it was no longer a true tree. Having just learned about graph contraction in graph theory, he decided to apply his knowledge to turn it back into a tree.

Specifically, Little T first needs to decide on the number of colors $m$ he will use, and then assign a color $c_i$ $(1\leq c_i\leq m)$ to each node $i$. Then, a new graph $G$ with $m$ nodes is constructed, where an edge exists between two nodes $i$ and $j$ $(i\neq j)$ in $G$ if and only if there exist two adjacent nodes $u, v$ in $T$ such that $c_u=i$ and $c_v=j$. Little T requires that the graph $G$ must be a tree.

For aesthetic reasons, Little T wants each color to be used by at least $1$ node and at most $k$ nodes. Can you help him construct such a scheme?

Input

A single line containing two integers $n$ and $k$, representing the number of levels of the full binary tree and the limit on the number of nodes for each color, respectively.

Output

The first line contains an integer $m$, the number of colors used.

The second line contains $2^{n+1}-1$ integers, where the $i$-th integer represents the color $c_i$ assigned to node $i$.

Examples

Input 1

1 12

Output 1

2
2 2 1

Input 2

2 12

Output 2

3
2 3 2 1 3 2 3

Note

In Example 1, the graph $G$ has $2$ nodes and $1$ edge $(1,2)$. The edge $(1,2)$ corresponds to the edges $(1,3)$ and $(2,3)$ in $T$.

In Example 2, the graph $G$ has $3$ nodes and $2$ edges $(1,3)$ and $(3,2)$. The edge $(1,3)$ corresponds to the edges $(4,2)$ and $(4,5)$ in $T$, and the edge $(3,2)$ corresponds to the edges $(2,1), (5,6), (3,7),$ and $(6,7)$ in $T$.

Constraints

For all test cases, $1\leq n\leq 20$, $12\leq k \leq 1.1\times 10^6$.

Subtask 1 (11 points): $n\leq 4$, $k=12$.

Subtask 2 (8 points): $k=1.1\times 10^6$.

Subtask 3 (15 points): $k=6\times 10^5$.

Subtask 4 (16 points): $k=5000$.

Subtask 5 (15 points): $k=200$.

Subtask 6 (35 points): $k=12$.