SOLVE
LATER
Masha likes numbers. She likes Fibonacci numbers even more, so that she represents all natural numbers as sum of Fibonacci numbers. She calls it Fibonacci number system.
Fibonacci numbers is a sequence f, which is defined as follows: \(f_0 = f_1 = 1\) and \(f_i = f_{i-1}+f_{i-2}\) for all \(i>1\).
Numbers in Fibonacci number system are represented as binary strings with no leading zeros and no two ones are consecutive. To represent natural number n in this system, one has to represent n as the sum of non-consecutive Fibonacci numbers: \(n=f_{i_1}+f_{i_2}+\dots+f_{i_m}\) such that \(i_j>0\) and \(|i_j-i_k|>1\) for all \(1 \le i, j \le m\), \(i \ne j\). For example, let's say \(n=7\), we can represent \(n = 7 = 2 + 5 = f_2 + f_4\), so 7 in Fibonacci number system is 1010, \(n=12\) represented as 10101 and \(n=1\) — as 1.
Masha got a piece of paper and started writing a big binary string s. Binary string s is formed as follows: initially she has empty string, then she appends Fibonacci number system representation of every natural number starting with 1 in increasing order. So the beginning of her string looks as follows: 110100101100010011010.... These are numbers from 1 to 7, their Fibonacci number system representations are: 1, 10, 100, 101, 1000, 1001, 1010.
Masha is very patient and hard-working, so she wrote a string s of length \(10^{18}\). You are given L and R, and you want to find a part of the string starting from L up to R.
Input consists of single line containing two integers L and R (\(1 \le L < R \le 10^{18}\); \(R - L \le 10^5\)).
Output binary string of length \((R-L)\): \(s_Ls_{L+1}\ldots s_{R-1}\).
These are \(s_1s_2 \ldots s_{19}\) of Masha's string: 1101001011000100110.