P1647 Lock

Given $N$ and $K$, you are to generate a sequence from $0$ to $2^N-1$. The first term of the sequence is $0$, and the sequence must satisfy the following three conditions: 1. The sequence has length $2^N$, and every number from $0$ to $2^N-1$ is used exactly once. 2. Any two adjacent numbers in the sequence are obtained by changing some bits of the previous number in its binary representation, where all the changed bits originally have the same value. That is, either change some $0$s to $1$s, or change some $1$s to $0$s, but not both at the same time. 3. When multiple sequences satisfy the first two conditions, the sequence must be lexicographically smallest. In other words, when generating the next number from the previous one, always choose the smallest possible value (of course, still satisfying the first two conditions). You are asked to find the maximum value among the first $K$ terms of this sequence. Output it in binary, with exactly $N$ bits, including leading zeros.

A single line with two integers $N, K$.

A binary number representing the answer.

### Sample Explanation The generated sequence is $[000,001,011,010,110,100,101,111]$. The maximum among the first $8$ terms is $111$. ### Constraints For all testdata, $1 \le N \le 50, 1 \le K \le 2^N$. Translated by ChatGPT 5