Друзья Вася Л. и Петя П. — талантливые мальчики, которые любят писать песни собственного сочинения. В будущем они хотят стать популярными музыкантами. Ребята знают: чтобы добиться успеха, нужно регулярно тренироваться. Именно поэтому они каждый день пишут по новой песне, совершенствуя свое мастерство.
Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(q\) вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции \(l\) до позиции \(r\) включительно. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке \(k\) раз, где \(k\) — порядковый номер соответствующей буквы в алфавите. Например, если Вася выбрал подстроку <<abbcb>>, то он повторит букву <<a>> один раз, каждую из букв <<b>> — по два раза, букву <<c>> — три раза, и полученная строка будет равна <<abbbbcccbb>>, ее длина равна 10. Вася интересуется именно длиной полученной строки.
Помогите Пете ответить Васе на его вопросы, а именно, для каждого из заданных вопросов определите длину строки, которую выпишет Вася.
Формат входных данных
В первой строке вводятся числа \(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\) строк — для каждого вопроса выведите длину строки, которую выпишет Вася.
Примечание
В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку <<aba>>, которая превратится в <<abba>>, а значит, ответ на этот вопрос равен 4. Во втором вопросе Вася рассматривает подстроку <<baca>>, которая превратится в <<bbaccca>>, а значит, ответ на этот вопрос будет равен 7. В третьем вопросе Вася рассматривает всю строку <<abacaba>>, которая превратится в <<abbacccabba>> — строку длины 11.
Для получение номера буквы можно использовать следующий код:
-
В языке python3 или pypy3 выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.
-
В языке c++ выражение x - 96, например a - 96 равно 1, а x - 96 равно 24.
-
В языке pascal выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
abacaba
1 3
2 5
1 7
|
4
7
11
|
|
2
|
7 4
abbabaa
1 3
5 7
6 6
2 4
|
5
4
1
5
|
|
3
|
13 7
sonoshikumiwo
1 5
2 10
7 7
1 13
4 8
2 5
3 9
|
82
125
9
191
62
63
97
|