Ssari and Bird's Pyramid

Time limit1sMemory limit256 MB

Summary

Count how many times a given letter appears in a requested pyramid row filled by repeating a word in alternating directions.

Level: Medium5 of 10
Topics: Math, Prefix sum
Solved: No attempts yet

Problem

Ssari and Bird had nothing at all to do, so they built a pyramid of height $N$ in the back yard and decided to write their favorite word on it. Row $i$ from the top has $i$ cells.

The word goes in one letter per cell, in a zigzag. Row 1 fills from left to right, row 2 from right to left, row 3 from left to right again, and so on. Once the word is written out, it starts over from its first letter.

For $N = 6$ and the word JANJETINA the pyramid comes out like this.

     J
    N A
   J E T
  J A N I
 A N J E T
N A J A N I

Bird picks a row number $a_i$ and an uppercase letter $c_i$ , then asks "how many times does $c_i$ appear in row $a_i$ ?". Answer Bird's $K$ questions and help Ssari out.

Input

The first line contains the height of the pyramid, $N$ ( $1 \le N \le 10^{18}$ ).

The second line contains a word made only of uppercase letters. The word is at most $10^6$ letters long.

The third line contains the number of rows Bird picked, $K$ ( $1 \le K \le 50000$ ).

Each of the next $K$ lines contains $a_i$ and $c_i$ separated by a space ( $1 \le a_i \le N$ , and $c_i$ is an uppercase letter).

Output

Print $K$ lines. Line $i$ holds the number of times $c_i$ appears in row $a_i$ of the pyramid.

Examples3

Example 1

Input

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

Expected output

Example 2
Input
```
5
A
5
1 A
2 A
3 A
4 A
5 B
```
Expected output
```
1
2
3
4
0
```
Example 3
Input
```
3
AB
3
2 A
2 B
3 B
```
Expected output
```
1
1
2
```