题目描述

小蓝在遗迹中发现了一面数字密码墙。密码墙可以看作一个长度为 $N$ 的字符串 $S$，字符串中只包含数字 $0$ 到 $9$。

小蓝可以从 $S$ 中截取任意一个非空连续子串，并将这个子串视作一个十进制整数。子串允许包含前导零，任意长度的前导零都不影响最终数值；若子串全部由数字 $0$ 构成，则无论子串长度是多少，其数值均为 $0$。例如，$05$ 和 $005$ 的数值都为 $5$，$0$ 和 $00$ 的数值均为 $0$。

如果两个子串的起止位置不同，即使它们对应的数值相同，也视为两种不同的截取方案。

现在小蓝有 $M$ 次尝试。第 $i$ 次尝试给出一个安全阈值区间 $[l_i, r_i]$。对于每次尝试，请你计算有多少种截取方案，使得截取得到的十进制数值落在 $[l_i, r_i]$ 内。

输入格式

第一行包含两个正整数 $N, M$，分别表示数字字符串的长度和询问次数。

第二行包含一个长度为 $N$ 的数字字符串 $S$。

接下来 $M$ 行，每行包含两个整数 $l_i, r_i$，表示一次查询的安全阈值区间。

输出格式

输出 $M$ 行。第 $i$ 行输出一个整数，表示第 $i$ 次查询的合法截取方案数。

5 3
00510
0 5
1 10
50 510

8
5
6

提示

【样例说明】

字符串为 $00510$。按数值统计所有非空连续子串，可以得到：

• 数值 $0$：子串为 $0$ 的截取方案共 $3$ 种，子串为 $00$ 的截取方案共 $1$ 种，合计 $4$ 种；
• 数值 $1$：子串为 $1$ 的截取方案共 $1$ 种；
• 数值 $5$：子串分别为 $5$、$05$、$005$ 的截取方案各 $1$ 种，合计 $3$ 种；
• 数值 $10$：子串为 $10$ 的截取方案共 $1$ 种；
• 数值 $51$：子串分别为 $51$、$051$、$0051$ 的截取方案各 $1$ 种，合计 $3$ 种；
• 数值 $510$：子串分别为 $510$、$0510$、$00510$ 的截取方案各 $1$ 种，合计 $3$ 种。

因此，区间 $[0, 5]$ 的答案为 $4+1+3=8$；区间 $[1, 10]$ 的答案为 $1+3+1=5$；区间 $[50, 510]$ 的答案为 $3+3=6$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N, M \le 1000$。

对于 $80\%$ 的评测用例，$1 \le N, M \le 5000$。

对于所有评测用例，$1 \le N, M \le 10^6$，$0 \le l_i \le r_i \le 100000$。