#CSPS2019A. [CSP-S2019] 格雷码

[CSP-S2019] 格雷码

Description

In daily routines, people prefer to sort binary strings of length nn lexicographically. For example, if we sort binary strings of length 22 increasingly, we will get: 0000, 0101, 1010, 1111.

Gray Code is a special sorting method to sort binary strings of length nn. It requires adjacent binary strings to have exactly one bit different. Specifically, the first string and the last string are also considered adjacent.

One example of binary strings of length 22s sorted in Gray Code is: 0000, 0101, 1111, 1010.

There can be multiple Gray Codes of length nn. The following is an algorithm for generating one of the Gray Codes:

  1. Gray Code of length 11 contains two binary strings of length 11, with the order: 00, 11.
  2. The first 2n2^n binary strings in Gray Code of length n+1n+1 can be generated by adding a prefix 00 to Gray Code of length nn (2n2^n binary strings of length nn in total) sorted in order.
  3. The last 2n2^n binary strings in Gray Code of length n+1n+1 can be generated by adding a prefix 11 to Gray Code of length nn (2n2^n binary strings of length nn in total) sorted in reverse order.

In short, Gray Code of length n+1n+1 is formed by adding a prefix 00 to sorted Gray Code of length nn, and adding a prefix 11 to reversely sorted Gray Code of length nn, to obtain 2n+12^{n+1} binary strings in total. Additionally, for the 2n2^n binary strings in Gray Code of length nn, we will label them from 00 to 2n12^n-1 in order.

Using this algorithm, Gray Code of length 22 can be generated as follow:

  1. It's known that Gray Code of length 11 is 00, 11.
  2. The first 22 strings in Gray Code of length 22 are: 0000, 0101. The last 22 are: 1111, 1010. Combining them, we get 0000, 0101, 1111, 1010. The labels are 0,1,2,30,1,2,3.

Gray Code of length 33 follows the same rule:

  1. It's known that Gray Code of length 22 is 0000, 0101, 1111, 1010.
  2. The first 44 strings in Gray Code of length 33 are: 000000, 001001, 011011, 010010. The last 44 are: 110110, 111111, 101101, 100100. Combining them, we get 000000, 001001, 011011, 010010, 110110, 111111, 101101, 100100. The labels are 0,1,2,,70,1,2,\dots,7.

You are given nn and kk. Find the kk-th binary string (the string with label kk) in Gray Code of length nn, generated by the algorithm above.

Input Format

The only line of the input contains two integers: nn and kk.

Output Format

Print a single binary string of length nn denoting the answer.

2 3
10
3 5
111

Constraints

For 50%50\% of the data, n10n\le 10;
For 80%80\% of the data, k5×106k \le 5\times 10^6;
For 95%95\% of the data, k2631k\le 2^{63}-1;
For 100%100\% of the data, 1n641\le n \le 64, 0k<2n0\le k < 2^n.