P6416 [COCI 2014/2015 #1] PIRAMIDA

Zoran and Tomislav are very bored today.

So, they repeatedly write their favorite string `JANJETINA` on a pyramid from left to right and from top to bottom following a certain pattern. This is what the pyramid looks like when it has only six layers:  Now they want to test you with a question: given a string $s$ and the number of layers $n$ of the pyramid, the string is written on the pyramid over and over again. Then there are $k$ queries. In the $i$-th query, you are asked how many times the character $c_i$ appears in layer $a_i$.

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 each contain an integer $a_i$ and a character $c_i$.

For each query, output one line with an integer representing the answer.

#### Explanation for Sample Input/Output 1 It corresponds to the example shown in the statement. #### Constraints - For $50\%$ of the testdata, it is guaranteed that $n \le 10^3$. - For $70\%$ of the testdata, it is guaranteed that $|s| \le 10^5$. - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^{18}$, $1 \le |s| \le 10^6$, $1 \le k \le 5 \times 10^4$, $1 \le a_i \le n$, and all characters in the input are uppercase letters. #### Note **The total score for this problem is $100$ points.** This problem is translated from Task 3 PIRAMIDA of [Croatian Open Competition in Informatics 2014/2015](https://hsin.hr/coci/archive/2014_2015) [Contest #1](https://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf). Translated by ChatGPT 5