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”。