Purple định nghĩa trọng số của xâu con liên tiếp từ ~L~ đến ~R~ của xâu ~S~ là tổng chênh lệch giữa vị trí đầu tiên và vị trí cuối cùng của từng kí tự trong xâu con đó. Ví dụ:

• Xâu con “abcba” sẽ có trọng số là ~(5-1)+(4-2)+(3-3)=6~.

Giải thích:

Xâu trên gồm ba kí tự khác nhau là ~a~, ~b~, ~c~

• Vị trí đầu tiên mà ~a~ xuất hiện là 1, vị trí cuối cùng mà ~a~ xuất hiện là 5.
• Vị trí đầu tiên mà ~b~ xuất hiện là 2, vị trí cuối cùng mà ~b~ xuất hiện là 4.
• Vị trí đầu tiên mà ~c~ xuất hiện là 3, vị trí cuối cùng mà ~c~ xuất hiện là 5.

Yêu cầu

Cho xâu ~S~ gồm ~N~ kí tự in thường và ~Q~ truy vấn ~L~, ~R~. Các bạn hãy giúp Tun tính trọng số của xâu con từ ~L~ đến ~R~ nhé.

Input

• Dòng 1 gồm 2 số nguyên dương ~N~, ~Q~ ~(1 \leq N, Q \leq 2*10^6)~;
• Dòng 2 là xâu ~S~ có ~N~ kí tự in thường;
• ~Q~ dòng tiếp theo mỗi dòng gồm 2 số nguyên dương ~L~, ~R~ ~(1 \leq L, R \leq N)~ biểu diễn truy vấn.

Output

In ra ~Q~ dòng là kết quả cho ~Q~ truy vấn.

Sample Input

7 3
abbdcad
2 4
1 7
3 6

Sample Output

1
9
0

Giải thích

• Trọng số đoạn ~[2, 4]~ là ~(3-2)+(4-4)=1~;
• Trọng số đoạn ~[1, 7]~ là ~(6-1)+(3-2)+(5-5)+(7-4) = 9~;
• Trọng số đoạn ~[3, 6]~ là ~(3-3)+(4-4)+(5-5)+(6-6) = 0~;

Subtask

• Có 30% số test ứng với 30% số điểm có ~N, Q \leq 10^3~;
• Có 30% số test ứng với 30% số điểm có ~N, Q ≤ 10^5~;
• 40% số test còn lại tương ứng với 40% số điểm không có giới hạn gì thêm.