Description

Who knows what 89 means, TAT. But Qu Pa knows that 89 is the second non-twin prime in the Fibonacci sequence. (Also, since 89 is laser-engraved on the gate... 89 will not appear in the later stories (problems)... but in this problem we still need to compute with 89.)

So it seems this phenomenon is related to the Fibonacci sequence. Now Qu Pa wants to know the digits from position M to position N of the cumulative sum formed from the Fibonacci sequence. The “cumulative sum” is the total from the 1st term times $10^{K}$ to the $K$-th term times $10^{1}$, i.e.,

Please write a program to help him.

Task: Given $M$, $N$, output the digits from position $M$ to $N$ of the cumulative sum.

The beginning of the cumulative sum: 1123595505...

Input Format

Two integers $M$ and $N$.

Output Format

The digits from position $M$ to position $N$ of the cumulative sum, without omitting leading or trailing zeros.

11 20

6179775280

Hint

Constraints: $10 \le M \le N \le 200000$. Since Qu Pa has already computed the first 10 digits, there is no use in knowing the digits after position 200000, right? Also, $0 < N - M + 1 \le 2000$. Precisely because Qu Pa needs at most 2000 digits, he requires your program to finish within 1 s.

Translated by ChatGPT 5