Trọng số của xâu con liên tiếp với độ dài 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ự xuất hiện trong xâu con đó. Ví dụ: Xâu con "abcab" sẽ có trọng số là ~(5 - 1) + (4 - 2) + (3 - 3) = 6~. Giải thích:

• 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à 3.

Yêu cầu: Cho xâu ~S~ gồm ~N~ ký tự trong khoảng 'a' đến 'z' và ~Q~ truy vấn ~L, R~. Bạn hãy giúp Purple 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 \le N, Q \le 2 \times 10^5~).
• Dòng 2 là xâu ~S~ có ~N~ ký tự trong khoảng 'a' đến 'z'.
• ~Q~ dòng tiếp theo mỗi dòng gồm 2 số nguyên dương ~L, R~ (~1 \le L \le R \le N~).

Output

• Ghi ra ~Q~ dòng kết quả cho ~Q~ truy vấn.