P2673 “Qu Pa's Number Game” T1 - Gatekeeper of the Number Kingdom

As soon as we arrive at the gate of the Number Kingdom, we see two huge numbers, 8 and 9, “laser-engraved” (please don't nitpick this word...) on the two sides of the gate. Qu Pa wonders what this means, so he comes to you.

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...

Two integers $M$ and $N$.

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

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