题目描述

给定一串长度为 $n$ 的数字，数字为 $0\sim 9$ 之间的任意一个，下标从 $1$ 记起。

然后进行 $m$ 次区间查询，每次查找区间 $[A,B]$ 的区间和，并在查询结束后将区间里的每一个数都 $+1$。特殊地，如果 $+1$ 前的数字为 $9$，那么 $+1$ 之后就变成了 $0$。

请输出每次查询的区间和。

输入格式

输入第一行包含两个整数 $n,m$。

第二行 $n$ 个数字字符，字符间无空格。

接下来的 $m$ 行，每行两个整数 $A,B$，表示查询区间 $[A,B]$。

输出格式

输出共 $m$ 行，每行为一次查询的区间和。

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 2.5\times 10^5$，$1\le m\le 10^5$，$1\le A,B\le n$。

说明

题目译自 COCI2007-2008 CONTEST #3 T6 REDOKS。