题目描述

咕咕鸡曾经写过一首悲伤的情歌，分享给了老淡陌。这首歌是一个由小写英文字母组成的字符串。老淡陌编了一些关于这首歌的问题。每个问题都是关于歌曲的一个小片段，从第l个字母到第r个字母。老淡陌考虑一个由这个段上的字符组成的子串，并重复子段中的每个字母k次，其中k是对应字母在字母表中的索引。例如，如果问题是关于子字符串“abbcb”，那么老淡陌重复字母“a”一次，每个字母“b”重复两次，字母“c”重复三次，所以结果字符串是“abbbbcccbb”，它的长度是10。老淡陌对结果字符串的长度感兴趣。

输入格式

第一行包含两个整数n和q(1$\\leq$n$\\leq$$1 \\cdot 10^5$,1$\\leq$q$\\leq$$1 \\cdot 10^5$)，表示歌曲的长度和问题的个数。

第二行包含一个字符串s -歌曲，由n个英文字母的小写字母组成。 问题包含在下面的q行中。每一行包含两个整数l和r(1$\\leq$l$\\leq$r$\\leq$n) -问题的边界。

输出格式

输出q行:对于每个问题打印由问题获得的字符串的长度

样例

7 3 
abacaba 
1 3 
2 5 
1 7 

4 
7 
11 

7 4 
abbabaa 
1 3 
5 7 
6 6 
2 4 

5 
4 
1 
5 

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

82 
125 
9 
191 
62 
63 
97 

提示

In the first example Vasya is interested in three questions. In the first question Vasya considers the substring "aba", that transforms to "abba", so the answer is equal to 4. In the second question Vasya considers "baca", that transforms to "bbaccca", so the answer is 7. In the third question Vasya considers the string "abacaba",that transforms to "abbacccabba" of length 11. （懒得翻译了，我知道你们看得懂） form:Codeforces Round#727 翻译转录 嵌入20-1 刘恺良 感谢董国梁学长对数据提供的支持 感谢我的好群友咕咕鸡和老淡陌的助力