ЕГЭ

Time limit4sMemory limit1024 MB

Summary

Given k and i, print the seven characters of the k-th string S_k starting at position i, where the strings follow the Thue-Morse doubling rule.

Level: Medium4 of 10
Topics: Bit manipulation, Math
Solved: No attempts yet

Problem

Igor loved computers since childhood. He played games on them, watched movies, and did many other enjoyable things. Sometimes he even wrote programs. He dreamed of getting into university and becoming a programmer. But Igor was not a very diligent student, so the day of the ЕГЭ informatics exam came as a complete surprise. Without a good ЕГЭ score, the dream will remain just a dream.

On a practice ЕГЭ, he got a task he did not know how to solve. The task asked for seven consecutive characters of the $k$ -th string, starting from the $i$ -th character. The strings are built by these rules:

$S_0 = 0$
$S_1 = 01$
$S_2 = 0110$
$S_3 = 01101001$
$S_4 = 0110100110010110$
$S_j = S_{j-1} + \overline{S_{j-1}}$ , where $\overline{S}$ is the string $S$ with all zeros replaced by ones and all ones replaced by zeros.

Igor asks you to help him solve this problem.

Input

The input file contains two integers $k$ and $i$ ( $2 \le k \le 63$ , $1 \le i \le 2^k - 6$ ).

Output

Print the seven characters of the $k$ -th string, starting from the $i$ -th character.

Examples2

Example 1
Input
```
3 2
```
Expected output
```
1101001
```
Example 2
Input
```
4 6
```
Expected output
```
0011001
```