Fibonacci substring
Tag(s):

## Combinatorics, Easy-Medium, Fibonacci, Math

Problem
Editorial
Analytics

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 format

Input consists of single line containing two integers $L$ and $R$ ($1 \le L < R \le 10^{18}$; $R - L \le 10^5$).

### Output format

Output binary string of length $(R-L)$: $s_Ls_{L+1}\ldots s_{R-1}$.

SAMPLE INPUT
11 20

SAMPLE OUTPUT
000100110

Explanation

These are $s_1s_2 \ldots s_{19}$ of Masha's string: 1101001011000100110.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

November Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Basic Math
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Math > Number Theory