시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 4 2 (50%) 2
문제
조란과 토미슬라프는 방학 중 할게 없어서 다양한 활동을 하고 있다. 오늘은 높이 N의 피라미드를 자신들이 가장 좋아하는 단어를 이용해 만들고 있다. 한 줄씩 쓰면서 방향을 바꾸면서 피라미드를 만든다. JANJETINA라는 단어를 이용해 만든 길이 $6$의 피라미드는 다음과 같다. ``` J N A J E T J A N I A N J E T N A J A N I ``` 토미슬라프는 이 피라미드에서 $K$개의 줄을 고른 뒤, 각각 $a_i$번째 줄에 대해 $c_i$라는 문자가 몇 번 나오는지 조란에게 물어본다. 조란을 도와 이 문제를 해결하는 프로그램을 작성하자.
입력
첫 줄엔 피라미드의 높이 $N$ $(1 \le N \le 10^{18})$이 주어진다. 다음 줄엔 알파벳 대문로 이루어진 단어가 주어진다. 이 단어의 길이는 $10^6$을 초과하지 않는다. 그 다음 줄엔 토미슬라프가 고른 $K$개의 줄이 주어진다 $(1 \le K \le 50,000)$. 그 다음 K개의 줄엔 토미슬라프의 질문을 나타내는 $a_i$, $c_i$ $(1 \le a_i \le N$, $c_i$는 알파벳 대문자$)$가 주어진다.
출력
$K$개의 줄을 출력한다. $i$번째 줄엔 피라미드의 $a_i$번 줄에 $c_i$가 몇 번 나타나는지 출력해야 한다.
힌트
#### 채점 정보 50%의 점수에 해당하는 테스트케이스에 대해 $1 \le N \le 1,000$이 성립한다. 70%의 점수에 해당하는 테스트케이스에 대해 단어의 길이가 $10^5$을 초과하지 않는다. ##### 입력 예제 1 ```6 JANJETINA 5 1 J 1 A 6 N 6 I 5 E ``` ##### 출력 예제 1 ```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 ```