格雷码

【题目描述】

通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按 字典序从小到大排列为：00, 01, 10, 11

格雷码（Gray Code）是一种特殊的n位二进制串排列法，它要求相邻的两个二进 制串间恰好有一位不同.特别地，第一个串与最后一个串也算作相邻。

所有2位二进制串按格雷码排列的一个例子为：00, 01, 11, 10。

n位格雷码不止一种，下面给出其中一种格雷码的生成算法：

1.1位格雷码由两个1位二进制串组成，顺序为：0, 1。

2.n + 1位格雷码的前2^n个二进制串，可以由依此算法生成的n位格雷码（总共 2^n个n位二进制串）按顺序排列，再在每个串前加一个前缀0构成。

3.n + 1位格雷码的后2^n个二进制串，可以由依此算法生成的n位格雷码（总共 2^n个n位二进制串）按逆序排列，再在每个串前加一个前缀1构成。

综上，n + 1位格雷码，由n位格雷码的2^n个二进制串按顺序排列再加前缀0,和 按逆序排列再加前缀1构成，共2^n+1个二进制串。另外，对于n位格雷码中的2^n个 二进制串，我们按上述算法得到的排列顺序将它们从0~2^n - 1编号。

按该算法，2位格雷码可以这样推出：

1.己知1位格雷码为0, 1

2.前两个格雷码为00, 01.后两个格雷码为11, 10。合并得到00, 01, 11, 10, 编号依次为0〜3。

同理，3位格雷码可以这样推出：

1.己知2位格雷码为：00, 01, 11 10。

2.前四个格雷码为：000, 001, 011.010。后四个格雷码为：110, 111, 101, 100。合并得到：000, 001. 011, 010, 110, 111. 101, 100,编号依次为 0 ~7。

现在给出n，k请你求出按上述算法生成的n位格雷码中的k号二进制串。

【输入格式】

从文件code.in中读入数据。

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

【输出格式】

输出到文件code.out中。

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

【样例1输入】

23

【样例1输出】

10

【样例1解释】

2位格雷码为：00, 01, 11. 10,编号从0〜3,因此3号串是10。

【样例2输入】

35

【样例2输出】

111

【样例2解释】

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

【数据范围】

对于50%的数据：n≤ 10

对于80%的数据：k≤5x10^6

对于95%的数据：k≤  2^63 - 1

对于 100% 的数据：1 ≤ n ≤ 64,0 ≤ k≤2^n