Problem Description

Usually, people are used to arranging all $n$-bit binary strings in lexicographical order. For example, all 2-bit binary strings in increasing lexicographical order are: 00, 01, 10, 11.

Gray Code is a special way to arrange $n$-bit binary strings. It requires that any two adjacent binary strings differ in exactly one bit. In particular, the first string and the last string are also considered adjacent.

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

There is more than one $n$-bit Gray Code. Below is one algorithm to generate a Gray Code:

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

In summary, the $(n + 1)$-bit Gray Code consists of the $2^n$ strings of the $n$-bit Gray Code in order with prefix 0, and the $2^n$ strings of the $n$-bit Gray Code in reverse order with prefix 1, making a total of $2^{n+1}$ binary strings. Also, for the $2^n$ binary strings in the $n$-bit Gray Code, we number them as $0 \sim 2^n - 1$ according to the order produced by the above algorithm.

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

1. The 1-bit Gray Code is 0, 1.
2. The first two Gray codes are 00, 01. The last two Gray codes are 11, 10. Merging them gives 00, 01, 11, 10, numbered from 0 to 3 in order.

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

1. The 2-bit Gray Code is: 00, 01, 11, 10.
2. The first four Gray codes are: 000, 001, 011, 010. The last four Gray codes are: 110, 111, 101, 100. Merging them gives: 000, 001, 011, 010, 110, 111, 101, 100, numbered from 0 to 7 in order.

Now you are 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 with two integers $n$ and $k$, as described in the statement.

Output Format

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

2 3

10

3 5

111

44 1145141919810

00011000111111010000001001001000000001100011

Hint

[Sample 1 Explanation]

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

[Sample 2 Explanation]

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

[Constraints]

For $50\%$ of the testdata: $n \leq 10$.

For $80\%$ of the testdata: $k \leq 5 \times 10^6$.

For $95\%$ of the testdata: $k \leq 2^{63} - 1$.

For $100\%$ of the testdata: $1 \leq n \leq 64$, $0 \leq k \lt 2^n$.

Translated by ChatGPT 5