Cho xâu ~S~ gồm ~N~ kí tự la tinh thường.

Yêu cầu:

Gồm ~Q~ truy vấn, mỗi truy vấn gồm bộ ba (~L,R,C~) và bạn phải in ra số lượng kí tự ~C~ trong các kí tự ~S_L,S_{(L+1)},…,S_R~.

Input:

Cho từ tệp IDP2004B.INP

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ (~N,Q≤10^5~ );
• Dòng thứ hai chứa xâu ~S~ gồm ~N~ kí tự latinh thường;
• ~Q~ dòng sau, mỗi dòng chứa bộ ba (~L,R,C~) (~1≤L≤R≤N;C∈~{a,b,…,z}).

  Output:

Ghi ra tệp IDP2004B.INP

Gồm ~Q~ dòng, mỗi dòng là kết quả tương ứng với mỗi truy vấn.

Ví dụ:

IDP2004B.INP

5 2
adbbc
1 1 a
2 5 b

IDP2004B.OUT

1
2