Vào ngày 8.8 hàng năm, hệ thống thương mại điện tử Taka tổ chức một đợt siêu sale. Năm nay, quy tắc sale hàng của Taka như sau:

• Các món hàng được phân ra 26 loại kí hiệu là các chữ cái thường từ '~a~' đến '~z~'
• Khi mua món hàng loại '~a~', khách hàng không được khuyến mãi gì cả.
• Khi mua món hàng loại '~b~', khách hàng được tặng thêm ~1~ món hàng tương ứng.
• Khi mua món hàng loại '~c~', khách hàng được tặng thêm ~2~ món hàng tương ứng.
• ..., tương tự với những loại hàng khác.
• Hệ thống sẽ cung cấp một chuỗi các món hàng, khách hàng sẽ chỉ được mua một đoạn con liên tiếp của chuỗi đó.

Lưu ý: Những món hàng được tặng sẽ không được dùng để nhận thêm khuyến mãi.

Vì là một người không giỏi Toán, Pusheen nhờ các bạn đếm số món hàng có thể nhận được khi mua một đoạn con từ ~l~ đến ~r~ nhé.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n, q~ ~(1≤n≤100000, 1≤q≤100000)~ — số món hàng, và số đoạn ~(l, r)~ Pusheen cần đếm.

• Dòng thứ hai chứa một chuỗi độ dài ~n~ — chuỗi các món hàng được hệ thống cung cấp, chỉ chứa các chữ cái thường Tiếng Anh.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~ ~(1≤l≤r≤n)~ — đoạn con liên tiếp các món hàng mà Pusheen cần đếm.

Dữ liệu ra

Gồm ~q~ dòng, mỗi dòng ghi tổng số món hàng mà Pusheen nhận được khi mua tất cả món hàng trong đoạn con ~(l, r)~.

Giới hạn

• Subtask 1 (35%): ~n, q \leq 1000~;
• Subtask 2 (65%): ~n, q \leq 100000~;

Sample Input 1

7 3
abacaba
1 3
2 5
1 7

Sample Output 1

4
7
11

Sample Input 2

13 7
sonoshikumiwo
1 5
2 10
7 7
1 13
4 8
2 5
3 9

Sample Output2

82
125
9
191
62
63
97

Giải thích

Ở ví dụ ~1~, query thứ ~2~, Pusheen được tặng thêm ~1~ món hàng loại '~b~', ~2~ món hàng loại '~c~'.