You have the string
s. You want to make a new line, writing each letter in it a number of times equal to the serial number of this letter in the alphabet. For example,
s = "abcdc", newline
s_new = "abbcccddddccc". We were wondering what the length of the string will be if you write out all the characters of the original string, starting with the character
l and ending with the character
r. Total we
k requests to you.
Input
In the first line, the program receives as input two numbers
n and
k (1<=n<=10
6, 1< ;=k<=10
6), where n is the string length,
k is the number of requests. The second line contains the string
s of length
n. The next
k lines contain the boundaries of the segments
l and
r (1 <= l <= r <= n). < code>l,
r - serial numbers of characters in a string, starting from
1.
Imprint
For each query print the length of the string you got. One number per line. Total
k lines.
Examples
| # |
Input |
Output |
| 1 |
5 3
abcd
15
23
3 5
| 13
5
10 |