RAM

해커들이 셸쇼크(Shellshock) 취약점으로 미르코의 컴퓨터에 침입했고, 시스템 전압을 높여서 마지막 2MB를 제외한 RAM을 거의 다 망가뜨렸다. 미르코의 컴퓨터에는 영어 대문자 A부터 Z까지로 이름을 붙인 하드디스크가 정확히 26개 있다. 다행히 미르코에게는 하드디스크 접근 기록을 담은 거대한 로그가 있다. 로그는 접근한 순서대로 하드디스크 이름을 나열한 문자열이다.

미르코는 해커의 공격을 다음과 같이 분석했다.

• 로그를 RAM에 올릴 수 있는 작은 파일 $N$개 $S_1, S_2, \ldots, S_N$으로 나누었다. 각 파일은 영어 대문자로 이루어진 문자열이고, 이 파일들을 순서대로 이어 붙이면 전체 로그가 된다.
• 파일을 하나씩 차례로 읽었다. 파일 $S_i$를 읽은 직후에는 로그의 처음부터 $S_i$의 끝까지 이어 붙인 문자열에서 마지막 $K_i$번의 접근 가운데 하드디스크 $H_i$에 접근한 횟수를 구했다.

미르코의 질문 $N$개에 모두 답하는 프로그램을 작성하시오.

첫째 줄에 파일의 개수 $N$이 주어진다. ($1 \le N \le 200\,000$)

다음 $2N$개의 줄은 두 줄씩 $N$개의 묶음으로 나뉜다. $i$번째 묶음은 다음과 같다.

• 첫 번째 줄에는 영어 대문자로 이루어진 문자열 $S_i$가 주어진다. ($1 \le |S_i| \le 4\,000$)
• 두 번째 줄에는 하드디스크 이름을 나타내는 영어 대문자 $H_i$와 접근 횟수 $K_i$가 공백으로 구분되어 주어진다. ($1 \le K_i \le \sum_{j=1}^{i} |S_j|$)

모든 파일 길이의 합 $\sum_{i=1}^{N} |S_i|$는 $2\,000\,000$ 이하이다.

$N$개의 줄에 미르코의 질문에 대한 답을 차례로 출력한다. $i$번째 줄에는 $S_1$부터 $S_i$까지 이어 붙인 문자열의 마지막 $K_i$개 문자 가운데 $H_i$와 같은 문자의 개수를 정확히 출력한다.