当老师在讲授氧化还原反应时，Luka 又在课堂上走神了。他没有专心听讲，而是在玩一些模拟拨盘。

一个模拟拨盘是一个可以显示 $0$ 到 $9$ 之间的一个数字的小装置。它还包含一个按钮，按下该按钮会将显示的数字增加 $1$（如果当前数字是 $9$，则会变为 $0$）。

Luka 的书桌上有 $N$ 个这样的拨盘，从左到右依次编号为 $1$ 到 $N$。他还有两张可以书写的纸。

Luka 的游戏开始时，他先将拨盘设置为某种初始状态，并将其记录在第一张纸上。接着，Luka 重复执行以下操作 $M$ 次：

• 选择两个整数 $A$ 和 $B$（$1 \le A \le B \le N$），并将它们记录在第一张纸上。
• 计算编号在 $A$ 到 $B$ 之间（含边界）的拨盘上数字的总和，并将该总和记录在第二张纸上。
• 将编号在 $A$ 到 $B$ 之间的所有拨盘上的按钮各按下一次。

就在他刚完成游戏时，老师发现了他，并没收了他所有的拨盘和第二张纸。

给定第一张纸上的内容，请帮助他计算出第二张纸上的数字。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 250000$，$1 \le M \le 100000$）。

第二行包含拨盘的初始状态，由 $N$ 个无空格的十进制数字组成。第一个数字是拨盘 1 上的初始数字，第二个数字是拨盘 2 上的初始数字，依此类推。

接下来的 $M$ 行，每行包含两个整数 $A$ 和 $B$（$1 \le A \le B \le N$）。

输出格式

输出 $M$ 行，即 Luka 计算出的总和，按照他计算的顺序依次输出。

子任务

在 $30\%$ 的测试数据中，数字 $N$ 和 $M$ 将小于 $1000$。

样例

输入样例 1

4 3
1234
1 4
1 4
1 4

输出样例 1

10
14
18

输入样例 2

4 4
1234
1 1
1 2
1 3
1 4

输出样例 2

1
4
9
16

输入样例 3

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

输出样例 3

17
23
1
19
5