lethienquan28052006 từ nhỏ đã rất đẹp trai, phong độ, rất nhiều cô gái theo đuổi. Nhưng lethienquan28052006 chỉ theo đuổi một người con gái xinh đệp duy nhất là phuongthao. phuongthao là một cô gái pro coder nên đã quyết định đưa ra một bài tập siêu dễ để thử sức của lethienquan28052006, bài tập có nội dung như sau:

Cho xâu \(S\) gồm \(N\) kí tự latinh thường.

Yêu cầu: Gồm \(Q\) truy vấn, mỗi truy vấn gồm bộ ba (\(𝐿, 𝑅, 𝐶\)) và bạn phải in ra số lượng kí tự \(𝐶\) trong các kí tự \(𝑆_𝐿, 𝑆_{𝐿+1}, … , 𝑆_𝑅.\)

Input

• Dòng đầu chứa hai số nguyên dương \(𝑁\) và \(Q\);
• Dòng thứ hai chứa xâu 𝑆 gồm 𝑁 kí tự latinh thường;
• \(𝑄\) dòng sau, mỗi dòng chứa bộ ba \((𝐿, 𝑅, 𝐶)\) (1 \leq \(𝐿\) \leq \(R\) \leq \(𝑁\); \(𝐶\) \(∈ {𝑎, 𝑏, … , 𝑧})\).

Output

• Gồm \(𝑄\) dòng, mỗi dòng là kết quả tương ứng với mỗi truy vấn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): \(N, Q \leq 10^5\).

Example

4 2
unhi
1 1 u
2 4 h 

1
1