Person in Charge

Problem Description

Typically, people are accustomed to arranging all $n$-bit binary strings in lexicographical order. For example, all 2-bit binary strings sorted in ascending lexicographical order are: $00$, $01$, $10$, $11$.

Gray Code is a special way to arrange $n$-bit binary strings, which requires that exactly one bit differs between adjacent binary strings. In particular, the first and last strings are also considered adjacent.

An example of 2-bit binary strings arranged in Gray Code order is: $00$, $01$, $11$, $10$.

There is more than one type of $n$-bit Gray Code. One algorithm for generating Gray Code is given below:

1. A 1-bit Gray Code consists of two 1-bit binary strings in the order: $0$, $1$.
2. The first $2^n$ binary strings of an $(n+1)$-bit Gray Code can be formed by taking the $n$-bit Gray Code (a total of $2^n$ $n$-bit binary strings) generated by this algorithm, arranging them in order, and prepending a prefix $0$ to each string.
3. The last $2^n$ binary strings of an $(n+1)$-bit Gray Code can be formed by taking the $n$-bit Gray Code (a total of $2^n$ $n$-bit binary strings) generated by this algorithm, arranging them in reverse order, and prepending a prefix $1$ to each string.

In summary, an $(n+1)$-bit Gray Code consists of the $2^n$ binary strings of the $n$-bit Gray Code arranged in order with a prefix $0$ added, followed by the same $2^n$ strings arranged in reverse order with a prefix $1$ added, totaling $2^{n+1}$ binary strings. Additionally, the $2^n$ binary strings in the $n$-bit Gray Code are numbered from $0 \sim 2^n - 1$ according to the order obtained by the above algorithm.

Using this algorithm, the 2-bit Gray Code can be derived as follows:

1. The 1-bit Gray Code is known to be $0$, $1$.
2. The first two Gray Code strings are $00$, $01$. The last two are $11$, $10$. Combining them gives $00$, $01$, $11$, $10$, numbered from $0$ to $3$ in sequence.

Similarly, the 3-bit Gray Code can be derived as follows:

1. The 2-bit Gray Code is known to be: $00$, $01$, $11$, $10$.
2. The first four Gray Code strings are: $000$, $001$, $011$, $010$. The last four are: $110$, $111$, $101$, $100$. Combining them gives: $000$, $001$, $011$, $010$, $110$, $111$, $101$, $100$, numbered from $0 \sim 7$ in sequence.

Given $n$ and $k$, please find the $k$-th binary string in the $n$-bit Gray Code generated by the above algorithm.

Input Format

A single line containing two integers $n$ and $k$, with meanings as described in the problem statement.

Output Format

A single line containing an $n$-bit binary string representing the answer.

Samples

2 3

10

3 5

111

Sample 1 Explanation

The 2-bit Gray Code is: $00$, $01$, $11$, $10$, numbered from $0 \sim 3$. Therefore, the 3rd string is $10$.

Sample 2 Explanation

The 3-bit Gray Code is: $000$, $001$, $011$, $010$, $110$, $111$, $101$, $100$, numbered from $0 \sim 7$. Therefore, the 5th string is $111$.

Sample 3

See code/code3.in and code/code3.ans in the contestant's directory.

Data Range

• For $50\%$ of the data: $n \le 10$.
• For $80\%$ of the data: $k \le 5 \times 10^6$.
• For $95\%$ of the data: $k \le 2^{63} - 1$.
• For $100\%$ of the data: $1 \le n \le 64$, $0 \le k \lt 2^n$.