Zoran and Tomislav don't really have anything important to do, so they spend their days doing various activities. Today, they built a pyramid of the height in the back garden and wrote their favorite word on it, repeating it from line to line and changing direction, as shown in the picture.
J N A J E T J A N I A N J E T N A J A N I
Pyramid of the height 6 marked with the word "JANJETINA"
Tomislav has now chosen lines of the pyramid, marked with , and has chosen a letter for each line. Then he asked Zoran tricky questions: "How many times does the letter appear in the row ?"
You are Zoran's counselor. Write a programme that will, for the given pyramid height and their favorite word, answer Tomislav's questions.
The first line of input contains the integer .
The second line of input contains a word that consists of only uppercase letters of the English alphabet. The word's length will not exceed .
The third line of input contains the integer , the number of lines Tomislav has chosen.
Each of the following lines contains the pair , uppercase letter of the English alphabet which represent Tomislav's questions.
Output lines. The line of output must contain a single integer – the number of appearances of letter in the row .
In test cases worth 50% of total points, will not exceed . In test cases worth 70% of total points, length of the string will not exceed .
Sample Input 1
6 JANJETINA 5 1 J 1 A 6 N 6 I 5 E
Sample Output 1
1 0 2 1 1
Clarification of Output for Sample Input 1
See the pyramid in the task statement.
Sample Input 2
5 A 5 1 A 2 A 3 A 4 A 5 B
Sample Output 2
1 2 3 4 0
Sample Input 3
3 AB 3 2 A 2 B 3 B
Sample Output 3
1 1 2