시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 131 21 17 19.101%

문제

싸리와 버드는 정말 할 게 없어서 뒷뜰에 높이가 N인 피라미드를 만들고 그 위에 좋아하는 단어를 쓰기로 했다. 아래 그림처럼 단어를 반복해서 지그재그 모양으로 써 내려간다. 

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

버드는 피라미드의 K개의 줄을 고르고 각 줄을 ai라고 하고, 그 줄의 문자를 골라 ci라고 한다. 그리고 싸리에게 "ai열에 ci가 몇 번 나오게?"라고 묻는다. 싸리를 도와 버드의 질문에 대답해보자.

입력

첫째 줄은 정수 N(1 ≤ N ≤ 1018)이 주어진다. 

둘째 줄은 단어가 주어진다. 단어의 길이는 106을 넘지 않는다.

셋째 줄은 정수 K(1 ≤ K ≤ 50,000)가 주어진다. (K는 버드가 고른 줄의 수이다.)

그 아래 K개의 줄에는 각각 ai, ci(1 ≤ ai ≤ N, ci는 알파벳) 쌍이 주어진다.

출력

K줄만큼 출력한다. i번째 줄은 ai열에 나오는 ci의 개수이다.

예제 입력

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

예제 출력

1
0
2
1
1

예제 입력 2

5
A
5
1 A
2 A
3 A
4 A
5 B

예제 출력 2

1
2
3
4
0

예제 입력 3

3
AB
3
2 A
2 B
3 B

예제 출력 3

1
1
2

힌트