English · Original
Chinese · Translation
Formal · Original
One Martian boy called Zorg wants to present a string of beads to his friend from the Earth — Masha. He knows that Masha likes two colours: blue and red, — and right in the shop where he has come, there is a variety of adornments with beads of these two colours. All the strings of beads have a small fastener, and if one unfastens it, one might notice that all the strings of beads in the shop are of the same length. Because of the peculiarities of the Martian eyesight, if Zorg sees one blue-and-red string of beads first, and then the other with red beads instead of blue ones, and blue — instead of red, he regards these two strings of beads as identical. In other words, Zorg regards as identical not only those strings of beads that can be derived from each other by the string turnover, but as well those that can be derived from each other by a mutual replacement of colours and/or by the string turnover.
It is known that all Martians are very orderly, and if a Martian sees some amount of objects, he tries to put them in good order. Zorg thinks that a red bead is smaller than a blue one. Let's put 0 for a red bead, and 1 — for a blue one. From two strings the Martian puts earlier the string with a red bead in the _i_\-th position, providing that the second string has a blue bead in the _i_\-th position, and the first two beads _i_ - 1 are identical.
At first Zorg unfastens all the strings of beads, and puts them into small heaps so, that in each heap strings are identical, in his opinion. Then he sorts out the heaps and chooses the minimum string in each heap, in his opinion. He gives the unnecassary strings back to the shop assistant and says he doesn't need them any more. Then Zorg sorts out the remaining strings of beads and buys the string with index _k_.
All these manupulations will take Zorg a lot of time, that's why he asks you to help and find the string of beads for Masha.
## Input
The input file contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 50;1 ≤ _k_ ≤ 1016) —the length of a string of beads, and the index of the string, chosen by Zorg.
## Output
Output the _k_\-th string of beads, putting 0 for a red bead, and 1 — for a blue one. If it s impossible to find the required string, output the only number _\-1_.
[samples]
## Note
Let's consider the example of strings of length 4 — 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. Zorg will divide them into heaps: {0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}. Then he will choose the minimum strings of beads in each heap: 0001, 0010, 0011, 0101, 0110. The forth string — 0101.
一个名叫佐尔的火星男孩想送给他在地球的朋友玛莎一串珠子。他知道玛莎喜欢两种颜色：蓝色和红色。在他去的商店里，有大量由这两种颜色珠子组成的装饰品。所有珠子串都带有一个小扣件，一旦解开扣件，就会发现商店里的所有珠子串长度都相同。由于火星人视力的特殊性，如果佐尔先看到一串红蓝相间的珠子，再看到另一串，其中红色和蓝色互换，他会认为这两串珠子是相同的。换句话说，佐尔认为，不仅可以通过翻转字符串相互得到的珠子串是相同的，而且可以通过颜色互换和/或翻转字符串相互得到的珠子串也是相同的。
众所周知，所有火星人都非常有条理，当一个火星人看到一些物体时，他会试图将它们有序排列。佐尔认为红色珠子比蓝色珠子小。我们用 0 表示红色珠子，用 1 表示蓝色珠子。当比较两个字符串时，火星人会将第 #cf_span[i] 位为红色珠子、而另一个字符串在第 #cf_span[i] 位为蓝色珠子的字符串排在前面，前提是这两个字符串的前 #cf_span[i - 1] 位完全相同。
首先，佐尔解开所有珠子串的扣件，将它们分成若干堆，使得每一堆中的珠子串在他看来是相同的。然后，他将这些堆排序，并从每堆中选出他认为最小的珠子串。他将多余的珠子串还给店员，说他不再需要它们了。接着，佐尔对剩余的珠子串进行排序，并购买第 #cf_span[k] 个字符串。
这些操作将花费佐尔大量时间，因此他请求你帮忙，找出送给玛莎的珠子串。
输入文件包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 50;1 ≤ k ≤ 1016]）——珠子串的长度和佐尔选择的字符串的索引。
请输出第 #cf_span[k] 个珠子串，用 0 表示红色珠子，用 1 表示蓝色珠子。如果无法找到所需的字符串，请仅输出数字 _-1_。
考虑长度为 4 的珠子串示例：0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110。佐尔会将它们分成如下堆：{0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}。然后他从每堆中选出最小的珠子串：0001, 0010, 0011, 0101, 0110。第四个字符串是 0101。
## Input
输入文件包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 50;1 ≤ k ≤ 1016]）——珠子串的长度和佐尔选择的字符串的索引。
## Output
请输出第 #cf_span[k] 个珠子串，用 0 表示红色珠子，用 1 表示蓝色珠子。如果无法找到所需的字符串，请仅输出数字 _-1_。
[samples]
## Note
考虑长度为 4 的珠子串示例：0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110。佐尔会将它们分成如下堆：{0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}。然后他从每堆中选出最小的珠子串：0001, 0010, 0011, 0101, 0110。第四个字符串是 0101。
**Definitions**
Let $\Sigma = \{0, 1\}$. Let $S = \Sigma^n$ be the set of all binary strings of length $n$.
For a string $s = s_1s_2\dots s_n \in S$, define the following operations:
1. **Reversal:** $s^R = s_n s_{n-1} \dots s_1$.
2. **Complement:** $s^C = \bar{s}_1 \bar{s}_2 \dots \bar{s}_n$, where $\bar{0} = 1$ and $\bar{1} = 0$.
3. **Reversal-Complement:** $s^{RC} = (s^R)^C = \bar{s}_n \bar{s}_{n-1} \dots \bar{s}_1$.
Define the orbit of $s$, denoted $\mathcal{O}(s)$, as the set of strings generated by these operations:
$$ \mathcal{O}(s) = \{s, s^R, s^C, s^{RC}\} $$
Let $\min_{\text{lex}}(\mathcal{O}(s))$ denote the lexicographically smallest string in the orbit of $s$.
**Set of Canonical Representatives**
Let $\mathcal{M}$ be the set of lexicographically minimal representatives for all unique orbits in $S$:
$$ \mathcal{M} = \{ \min_{\text{lex}}(\mathcal{O}(s)) \mid s \in S \} $$
Equivalently:
$$ \mathcal{M} = \{ s \in S \mid s \le_{\text{lex}} s^R \land s \le_{\text{lex}} s^C \land s \le_{\text{lex}} s^{RC} \} $$
**Ordering**
Let the elements of $\mathcal{M}$ be ordered lexicographically:
$$ m_1 <_{\text{lex}} m_2 <_{\text{lex}} \dots <_{\text{lex}} m_{|\mathcal{M}|} $$
**Input**
Integers $n$ and $k$, where $2 \le n \le 50$ and $1 \le k \le 10^{16}$.
**Objective**
Determine the output $Y$ defined as:
$$ Y = \begin{cases} m_k & \text{if } 1 \le k \le |\mathcal{M}| \\ -1 & \text{if } k > |\mathcal{M}| \end{cases} $$
API Response (JSON)
{
"problem": {
"name": "E. Beads",
"description": {
"content": "One Martian boy called Zorg wants to present a string of beads to his friend from the Earth — Masha. He knows that Masha likes two colours: blue and red, — and right in the shop where he has come, the",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 65536
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF8E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "One Martian boy called Zorg wants to present a string of beads to his friend from the Earth — Masha. He knows that Masha likes two colours: blue and red, — and right in the shop where he has come, the...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "一个名叫佐尔的火星男孩想送给他在地球的朋友玛莎一串珠子。他知道玛莎喜欢两种颜色：蓝色和红色。在他去的商店里，有大量由这两种颜色珠子组成的装饰品。所有珠子串都带有一个小扣件，一旦解开扣件，就会发现商店里的所有珠子串长度都相同。由于火星人视力的特殊性，如果佐尔先看到一串红蓝相间的珠子，再看到另一串，其中红色和蓝色互换，他会认为这两串珠子是相同的。换句话说，佐尔认为，不仅可以通过翻转字符串相互得到的珠子...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions**\n\nLet $\\Sigma = \\{0, 1\\}$. Let $S = \\Sigma^n$ be the set of all binary strings of length $n$.\nFor a string $s = s_1s_2\\dots s_n \\in S$, define the following operations:\n1. **Reversal:*...",
"is_translate": false,
"language": "Formal"
}
]
}