Yunyi is given a sentence consisting of lowercase Latin letters and spaces, ~S~, and he has to determine which language the sentence is written in. One way that he knows of determining the language is by counting letter frequencies in certain sections of the sentence.
Yunyi will give you ~Q~ queries of the form
i j c, which asks for the frequency of letter ~c~ between indices ~i~ and ~j~ (inclusive) ~(1 \le i \le j \le |S|)~. Note that spaces (
) are not considered letters, and therefore will not be queried.
The first line will contain the sentence ~S\ (1 \le |S| \le 10^6)~.
The second line will contain the integer ~Q\ (1 \le Q \le 10^5)~.
The next ~Q~ lines will each contain a valid query as defined above.
The sentence will only consist of lowercase latin characters and spaces. There will only be one space between any 2 words, and there will be no leading/trailing spaces.
For each query, print the frequency of the letter ~c~ between indices ~i~ and ~j~ (inclusive).
Subtask 1 [10%]
~|S|, Q \le 1\ 000~.
Subtask 2 [90%]
No further constraints.
this is a very interesting sentence and you will agree 4 1 4 h 6 6 p 15 26 t 1 54 e
1 0 2 8