← 返回题目列表

Codeforces · 1539/B

B. 情歌

中文机器翻译题面 查看原题

Petya曾经写过一首悲伤的情歌并分享给Vasya。歌曲是由小写英文字母组成的字符串。 Vasya 提出了关于这首歌的 $$$q$$$ 问题。每个问题都是关于歌曲的一个子片段,从第 $$$l$$$ 个字母到第 $$$r$$$ 个字母。 Vasya 考虑由该段上的字符组成的子字符串,并将子段中的每个字母重复 $$$k$$$ 次,其中 $$$k$$$ 是字母表中相应字母的索引。例如,如果问题是关于子字符串“abbcb”,则 Vasya 会重复字母“a”一次,每个字母“b”重复两次,字母“c”重复三次,因此生成的字符串为“abbbbccccbb”,其长度为 $$$10$$$。Vasya 对生成的字符串的长度感兴趣。

帮助Petya求出Vasya获得的每个字符串的长度。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\leq n\leq 100\,000$$$, $$$1\leq q \leq 100\,000$$$) — 歌曲的长度和问题的数量。

第二行包含一个字符串$$$s$$$——歌曲,由$$$n$$$小写英文字母组成。

Vasya 的问题包含在接下来的 $$$q$$$ 行中。每行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) - 问题的边界。

输出

打印 $$$q$$$ 行:对于每个问题,打印 Vasya 获得的字符串的长度。

示例

输入 #1

7 3
abacaba
1 3
2 5
1 7

输出 #1

4
7
11

输入 #2

7 4
abbabaa
1 3
5 7
6 6
2 4

输出 #2

5
4
1
5

输入 #3

13 7
sonoshikumiwo
1 5
2 10
7 7
1 13
4 8
2 5
3 9

输出 #3

82
125
9
191
62
63
97

注意

在第一个示例中,Vasya 对三个问题感兴趣。在第一个问题中,Vasya 考虑了子字符串“aba”,它会转换为“abba”,因此答案等于 $$$4$$$。在第二个问题中,Vasya 认为“baca”会转换为“bbaccca”,所以答案是 $$$7$$$。在第三个问题中,Vasya 考虑字符串“abacaba”,该字符串转换为长度为 $$$11$$$ 的“abbacccabba”。