SOLVE
LATER
Anna as well as Masha likes Fibonacci numbers and she also represents all natural numbers as sum of Fibonacci numbers. Girls call 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=s_1s_2s_3 \ldots\). 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}\). Anna found a piece of paper with a part of string s, written by Masha, along with integers L and R. She guessed that this piece of paper contains \(s_Ls_{L+1} \ldots s_R\). Anna likes substrings, so she wants to know number of occurrences of substrings 00
, 01
, 10
and 11
on this piece of paper.
Input format
Input consists of single line containing two integers L and R.
Constraints
\(1 \le L \le R \le 10^{18}\)
Output format
Output four integers \(c_{00}\), \(c_{01}\), \(c_{10}\) and \(c_{11}\) — number of occurrences of substrings 00
, 01
, 10
and 11
in string \(s_Ls_{L+1} \ldots s_R\), respectively.
A piece of paper for sample test contains string 000100110
.