一个名叫佐格的火星男孩想要向他来自地球的朋友玛莎赠送一串珠子。他知道玛莎喜欢两种颜色:蓝色和红色——而在他来的商店里,有各种各样带有这两种颜色的珠子的装饰品。所有的珠串都有一个小扣子,解开它就会发现店里所有的珠串都是一样长的。由于火星人视力的特殊性,如果佐格首先看到一串蓝色和红色的珠子,然后看到另一串珠子,其中红色珠子而不是蓝色珠子,以及蓝色珠子而不是红色珠子,他会认为这两串珠子是相同的。换句话说,Zorg 不仅认为那些可以通过串线翻转而彼此衍生的珠串是相同的,而且还认为那些可以通过颜色相互替换和/或串线翻转而彼此衍生的珠串是相同的。
众所周知,所有火星人都非常有秩序,如果火星人看到一定数量的物体,他会尝试将它们排列整齐。佐格认为红色珠子比蓝色珠子小。让我们为红色珠子输入 0,为蓝色珠子输入 1。火星人将两根绳子中的第 i 个位置有一个红色珠子的绳子先放在第 i 个位置,前提是第二根绳子的第 i 个位置有一个蓝色珠子,并且前两个珠子 i-1 是相同的。
首先,佐格解开所有的珠串,并将它们分成小堆,在他看来,每堆中的串都是相同的。然后他对这些堆进行排序,并在每个堆中选择他认为最小的字符串。他把不必要的字符串还给店员,并说他不再需要它们了。然后Zorg将剩余的珠串分类出来并购买索引为k的串。
所有这些操作都会花费佐格很多时间,这就是为什么他要求你帮忙找到玛莎的珠串。
输入
输入文件包含两个整数 n 和 k (2 ≤ n ≤ 50;1 ≤ k ≤ 1016) — 由 Zorg 选择的一串珠子的长度以及该串的索引。
输出
输出第 k 串珠子,红色珠子为 0,蓝色珠子为 1。如果找不到所需的字符串,则输出唯一的数字-1。
示例
输入 #1
4 4
输出 #1
0101
注意
让我们考虑长度为 4 的字符串的示例 - 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110。Zorg 会将它们分为堆:{0001、0111、1000、1110}、{0010、0100、1011、1101}、{0011、1100}、{0101、1010}、{0110、1001}。然后他会在每堆中选择最少的珠串:0001、0010、0011、0101、0110。第四串 - 0101。