题目描述

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 \leq n \leq 100\,000$，$1 \leq q \leq 100\,000$），分别表示歌曲的长度和问题的数量。

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

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示每个问题的区间。

输出格式

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

说明/提示

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

由 ChatGPT 4.1 翻译

样例

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