У вас есть строка
s. Вы хотите сделать новую строку, записывая в ней каждую букву количество раз равное порядковому номеру этой буквы в алфавите. Например,
s = "abcdc", новая строка
s_new = "abbcccddddccc". Нам стало интересно, какая получится у вас длина строки, если выписать все символы исходной строки, начиная с символа
l и заканчивая символом
r. Всего у нас
k запросов к вам.
Входные данные
В первой строке программа получает на вход два числа
n и
k (1<=n<=10
6, 1<=k<=10
6), где n - длина строки,
k - количество запросов. Во второй строке записана строка
s длиной
n. В следующих
k строках расположены границы отрезков
l и
r (1 <= l <= r <= n).
l,
r - порядковые номера символов в строке, начиная с
1.
Выходные данные
Для каждого запроса выведите длину строки, которая у вас получилась. По одному числу в строке. Всего
k строк.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 3
abcdc
1 5
2 3
3 5 |
13
5
10 |