싸리와 버드의 피라미드

싸리와 버드는 정말 할 게 없어서 뒷뜰에 높이가 $N$인 피라미드를 쌓고 그 위에 좋아하는 단어를 적기로 했다. 위에서 $i$번째 줄에는 칸이 $i$개 있다.

단어를 한 글자씩 떼어 지그재그로 채워 넣는다. 첫째 줄은 왼쪽에서 오른쪽으로, 둘째 줄은 오른쪽에서 왼쪽으로, 셋째 줄은 다시 왼쪽에서 오른쪽으로 채운다. 단어를 끝까지 쓰면 그 단어의 첫 글자부터 다시 이어서 쓴다.

$N = 6$이고 단어가 JANJETINA이면 피라미드는 이렇게 완성된다.

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

버드는 줄 번호 $a_i$와 알파벳 대문자 $c_i$를 골라 "$a_i$번째 줄에 $c_i$가 몇 번 나오지?"라고 묻는다. 버드의 질문 $K$개에 답해 싸리를 도와주자.

첫째 줄에 피라미드의 높이 $N$ ($1 \le N \le 10^{18}$)이 주어진다.

둘째 줄에 알파벳 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 $10^6$을 넘지 않는다.

셋째 줄에 버드가 고른 줄의 수 $K$ ($1 \le K \le 50000$)가 주어진다.

이어지는 $K$개의 줄에 $a_i$와 $c_i$가 공백을 사이에 두고 주어진다. ($1 \le a_i \le N$이고 $c_i$는 알파벳 대문자이다.)

$K$개의 줄을 출력한다. $i$번째 줄에는 피라미드의 $a_i$번째 줄에 $c_i$가 나오는 횟수를 출력한다.