COCI '14 Contest 1 #3 Piramida

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
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 N 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 K lines of the pyramid, marked with a_i, and has chosen a letter c_i for each line. Then he asked Zoran K tricky questions: "How many times does the letter c_i appear in the row a_i?"

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 N (1 \le N \le 10^{18}).
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 10^6.
The third line of input contains the integer K (1 \le K \le 50\,000), the number of lines Tomislav has chosen.
Each of the following K lines contains the pair a_i, c_i (1 \le a_i \le N, c_i uppercase letter of the English alphabet) which represent Tomislav's questions.

Output

Output K lines. The i^{th} line of output must contain a single integer – the number of appearances of letter c_i in the row a_i.

Scoring

In test cases worth 50% of total points, N will not exceed 1\,000. In test cases worth 70% of total points, length of the string will not exceed 10^5.

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

Comments


  • 2
    haytam  commented on Nov. 14, 2017, 4:36 p.m.

    why i get mle the judge is joking me he input big numbers and i get mle


    • 2
      A_H_Ghaznavi  commented on June 17, 2019, 5:13 a.m. edited

      The judge isn't joking you :)

      Likely you used dp to solve the problem and you created a big array! But you can use another creative idea to reduce memory.

      You can create 26 vector and for any letter like c you save some numbers like x such that stinrg_x=c in sorted form. Then create a function f(x,y,z) to find number of letter z in range [x,y] and use binary search.

      sorry for my poor English!


  • 1
    fungucide420  commented on March 28, 2017, 10:15 a.m. edited

    I don't know what I did wrong. 5th batch case and onward I have WA. Can someone give me a hint on what I did wrong?


    • 2
      A_H_Ghaznavi  commented on June 17, 2019, 5:15 a.m. edited

      Mybe for big numbers (numbers like x so that 10^{18}<x)! I got WA for that too but I fixed it!


  • 0
    XIAOAGE  commented on Nov. 29, 2015, 11:57 a.m.

    dont know how to solve this


  • 0
    Amplify  commented on Nov. 14, 2015, 10:52 p.m.

    all test cases after the 5th one fail... :(