## COCI '14 Contest 1 #3 Piramida

View as PDF

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

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.

#### Input

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

Output lines. The line of output must contain a single integer – the number of appearances of letter in the row .

#### Scoring

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

#### Explanation for Sample 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