Problem Description

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.

Input Format

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 Format

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

4 3
1234
1 4
1 4
1 4

10
14
18

4 4
1234
1 1
1 2
1 3
1 4

1
4
9
16

7 5
9081337
1 3
3 7
1 3
3 7
1 3

17
23
1
19
5

Hint

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 CONTEST #3 T6 REDOKS。

Translated by ChatGPT 5