Problem X: CSP-S2019 D1T1：格雷码（code）

Problem X: CSP-S2019 D1T1：格雷码（code）

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitProblemListSolved: 4Submit Num: 8StatisticsShowOff!

Description

通常，人们习惯将所有 nnn 位二进制串按照字典序排列，例如所有 222 位二进制串按字典序从小到大排列为：000000，010101，101010，111111。
格雷码（Gray Code）是一种特殊的 nnn 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。
所有 222 位二进制串按照格雷码排列的一个例子为：000000，010101，111111，101010。
nnn 位格雷码不止一种，下面给出其中一种格雷码的生成算法：
  1. 1 位格雷码由两个一位二进制串组成，顺序为：000，111。
  2. n+1n+1n+1 位格雷码的前 2n2^n2n 个二进制串，可以由依此算法生成的 nnn 位格雷码（总共 2n2^n2n 个 nnn 位二进制串）按顺序排列，再在每个串前加一个前缀 000 构成。
  3. n+1n+1n+1 位格雷码的后 2n2^n2n 个二进制串，可以由依此算法生成的 nnn 位格雷码（总共 2n2^n2n 个 nnn 位二进制串）按逆序排列，再在每个串前加一个前缀 111 构成。
综上，n+1n+1n+1 位格雷码，由 nnn 位格雷码的 2n2^n2n 个二进制串按顺序排列再加前缀 000，和逆序排列再加前缀 111 构成，共 2n+12^{n+1}2n+1 个二进制串。另外，对于 nnn 位格雷码中的 2n2^n2n 个二进制串，我们按上述算法得到的排列顺序将它们从 000 ~ 2n−12^n-12n−1 编号。
按该算法，222 位格雷码可以这样推出：
  1. 已知 111 位格雷码为 000，111。
  2. 前两个格雷码为 00\textit{\textbf{0}}000，01\textit{\textbf{0}}101。后两个格雷码为 11\textit{\textbf{1}}111，10\textit{\textbf{1}}010。合并得到 000000，010101，111111，101010，编号一次为 000 ~ 333。
同理，333 位格雷码可以这样推出：
  1. 已知 222 位格雷码为：000000，010101，111111，101010。
  2. 前四个格雷码为：000\textit{\textbf{0}}00000，001\textit{\textbf{0}}01001，011\textit{\textbf{0}}11011，010\textit{\textbf{0}}10010。后四个格雷码为：110\textit{\textbf{1}}10110，111\textit{\textbf{1}}11111，101\textit{\textbf{1}}01101，100\textit{\textbf{1}}00100。合并得到：000000000，001001001，011011011，010010010，110110110，111111111，101101101，100100100，编号依次为 000 ~ 777。
现在给出 n,kn,kn,k，请你求出按上述算法生成的 nnn 位格雷码中的 kkk 号二进制串。

Input

仅一行两个整数 n,kn,kn,k，意义见题目描述。

Output

仅一行一个 nnn 位二进制串表示答案。

Constraints

对于 505050% 的数据：n≤10n \le 10n≤10
对于 808080% 的数据：k≤5×106k \le 5 \times 10^6k≤5×106
对于 959595% 的数据：k≤263−1k \le 2 ^ {63}-1k≤263−1
对于 100100100% 的数据：1≤n≤641 \le n \le 641≤n≤64，0≤k<2n0 \le k \lt 2^n0≤k<2n。

Sample 1 Input 

2 3

Sample 1 Output 

10
2 位格雷码为：000000，010101，111111，101010，编号从 000 ~ 333，因此 333 号串是 101010。

Sample 2 Input 

3 5

Sample 2 Output 

111
3 位格雷码为：000，001，011，010，110，111，101，100，编号从 0∼7，因此 5 号串是 111。

Sample 3 Input 

44 1145141919810

Sample 3 Output 

00011000111111010000001001001000000001100011

HINT

相同题目：洛谷P5657。
Submit