Đếm ký tự trong đoạn

Cho xâu \(s\) gồm \(n\) chữ cái in thường (các ký tự đánh số từ \(1\) đến \(n\)) và \(q\) câu hỏi. Mỗi câu hỏi gồm hai số \(l, r\) và một chữ cái \(c\): hãy đếm số lần chữ cái \(c\) xuất hiện trong đoạn \(s_l s_{l+1} \dots s_r\).

Input

• Dòng đầu tiên chứa xâu \(s\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa số nguyên dương \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le n\)) và một chữ cái in thường \(c\).

Output

• In ra \(q\) dòng, dòng thứ \(j\) là câu trả lời cho câu hỏi thứ \(j\).

Subtask

• \(50\%\) số test: \(n, q \le 1000\).
• \(50\%\) số test: không có ràng buộc gì thêm.

Sample Input 1

banana
3
1 6 a
2 4 n
1 3 z

Sample Output 1

3
1
0

Notes

Đoạn \([2, 4]\) là ana, có \(1\) chữ n.