暂无测试数据。

Description

通常，人们习惯将所有 \(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\) 号二进制串。

Format

Input

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

Output

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

Sample 1

Input

2 3

Output

10

Sample 2

Input

3 5

Output

111

Limitation

Data

对于 \(50\%\) 的数据：\(n \le 10\)；

对于 \(80\%\) 的数据：\(k \le 5 \times 10^6\)；

对于 \(95\%\) 的数据：\(k \le 2^{63}-1\)；

对于 \(100\%\) 的数据：\(1 \le n \le 64,0 \le k<2^n\)。

Time and Space

1s, 125MB.

Source

CSP-S 2019 Day1 A

update by Shuchong