题目描述

Petya 曾经写过一首悲伤的情歌，并把它分享给了 Vasya。这首歌是一个只包含小写英文字母的字符串。Vasya 针对这首歌提出了 q 个问题。每个问题都涉及到歌曲的一个子区间，从第 l 个字母到第 r 个字母。Vasya 会取出该区间对应的子串，并将子串中的每个字母重复 k 次，其中 k 是该字母在英文字母表中的序号。例如，如果问题涉及的子串是 "abbcb"，那么 Vasya 会将字母 'a' 重复 1 次，每个字母 'b' 重复 2 次，字母 'c' 重复 3 次，得到的新字符串为 "abbbbcccbb"，其长度为 10。Vasya 想知道每次得到的新字符串的长度。
请帮助 Petya 计算 Vasya 得到的每个字符串的长度。

输入

第一行包含两个整数 n 和 q（1≤n≤100000，1≤q≤100000），分别表示歌曲的长度和问题的数量。
第二行包含一个字符串 s，表示歌曲，由 n 个小写英文字母组成。
接下来的 q 行，每行包含两个整数 l 和 r（1≤l≤r≤n），表示每个问题的区间。

输出

输出 q 行，对于每个问题，输出 Vasya 得到的新字符串的长度。

输入样例

7 3
abacaba
1 3
2 5
1 7

4
7
11

说明/提示

在样例中，Vasya 关心三个问题。第一个问题中，Vasya 取出的子串是 "aba"，变换后得到 "abba"，答案为 4。第二个问题中，子串为 "baca"，变换后得到 "bbaccca"，答案为 7。第三个问题中，子串为 "abacaba"，变换后得到 "abbacccabba"，长度为 11。