Problem Description

Xiao Lan found a digital password wall in some ruins. The password wall can be seen as a string $S$ of length $N$, and the string contains only digits from $0$ to $9$.

Xiao Lan can take any non-empty contiguous substring of $S$ and treat this substring as a decimal integer. Leading zeros are allowed, and any number of leading zeros does not affect the final value. If the substring consists entirely of digit $0$, then no matter how long the substring is, its value is $0$. For example, the values of $05$ and $005$ are both $5$, and the values of $0$ and $00$ are both $0$.

If two substrings have different start or end positions, then even if their values are the same, they are considered two different extraction plans.

Now Xiao Lan has $M$ attempts. In the $i$-th attempt, a security threshold interval $[l_i, r_i]$ is given. For each attempt, please compute how many extraction plans make the extracted decimal value fall within $[l_i, r_i]$.

Input Format

The first line contains two positive integers $N, M$, representing the length of the digit string and the number of queries.

The second line contains a digit string $S$ of length $N$.

The next $M$ lines each contain two integers $l_i, r_i$, representing the security threshold interval of one query.

Output Format

Output $M$ lines. The $i$-th line outputs one integer, representing the number of valid extraction plans for the $i$-th query.

5 3
00510
0 5
1 10
50 510

8
5
6

Hint

Sample Explanation

The string is $00510$. If we count all non-empty contiguous substrings by their values, we get:

• Value $0$: there are $3$ extraction plans for substring $0$, and $1$ extraction plan for substring $00$, for a total of $4$ plans.
• Value $1$: there is $1$ extraction plan for substring $1$.
• Value $5$: the substrings $5$, $05$, and $005$ each have $1$ extraction plan, for a total of $3$ plans.
• Value $10$: there is $1$ extraction plan for substring $10$.
• Value $51$: the substrings $51$, $051$, and $0051$ each have $1$ extraction plan, for a total of $3$ plans.
• Value $510$: the substrings $510$, $0510$, and $00510$ each have $1$ extraction plan, for a total of $3$ plans.

Therefore, the answer for interval $[0, 5]$ is $4+1+3=8$. The answer for interval $[1, 10]$ is $1+3+1=5$. The answer for interval $[50, 510]$ is $3+3=6$.

Constraints

For $30\%$ of the testdata, $1 \le N, M \le 1000$.

For $80\%$ of the testdata, $1 \le N, M \le 5000$.

For all testdata, $1 \le N, M \le 10^6$, $0 \le l_i \le r_i \le 100000$.

Translated by ChatGPT 5