P6357 [COCI 2007/2008 #3] REDOKS

You are given a sequence of digits of length $n$. Each digit is any one of $0 \sim 9$, and the indices start from $1$. Then perform $m$ range queries. For each query, find the sum of the digits in the range $[A, B]$, and after the query, add $1$ to every digit in this range. In particular, if a digit is $9$ before adding $1$, then it becomes $0$ after adding $1$. Output the range sum for each query.

The first line contains two integers $n, m$. The second line contains $n$ digit characters, with no spaces between them. The next $m$ lines each contain two integers $A, B$, representing the query range $[A, B]$.

Output $m$ lines in total. Each line contains the range sum for one query.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 2.5 \times 10^5$, $1 \le m \le 10^5$, and $1 \le A, B \le n$. #### Notes **This problem is translated from [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #3](https://hsin.hr/coci/archive/2007_2008/contest3_tasks.pdf) *T6 REDOKS***。 Translated by ChatGPT 5