Problem Background

Zoran and Tomislav are feeling bored today.

Problem Description

They decided to write their favorite string JANJETINA repeatedly on a tower in a specific pattern, from left to right and top to bottom.

Here is an example of a tower with six levels:

Now, they want to test you with a question: Given a string \( s \) and the number of levels \( n \) in the tower, you will be asked \( k \) questions. Each question \( i \) asks how many times character \( c_i \) appears in level \( a_i \).

Input Format

The first line contains an integer \( n \).

The second line contains a string \( s \).

The third line contains an integer \( k \).

The next \( k \) lines contain an integer \( a_i \) and a character \( c_i \).

Output Format

For each question, output a single integer on a new line.

Sample Input and Output

Sample Input #1

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

Sample Output #1

1
0
2
1
1

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

Notes

Sample Input and Output 1 Explanation

This is the example provided in the problem.

Data Constraints

• For 50% of the test cases, \( n \leq 10^3 \).
• For 70% of the test cases, \( |s| \leq 10^5 \).
• For 100% of the test cases, \( 1 \leq n \leq 10^{18} \), \( 1 \leq |s| \leq 10^6 \), \( 1 \leq k \leq 5 \times 10^4 \), \( 1 \leq a_i \leq n \), and the characters in the input are uppercase letters.

Note

This problem is worth 100 points.

This problem is translated from the Croatian Open Competition in Informatics 2014/2015 Contest #1 T3 PIRAMIDA.

见题面 Input 部分

见题面 Output 部分