32167번 - a11y

문제

당신은 a11y라는 단어를 들어본 적이 있는가? 이는 accessibility (접근성)을 줄인 축약어로, a와 y 사이 11개의 문자가 있는 것을 뜻한다. 이와 비슷한 축약어로 k8s (Kubernetes), i18n (internationalization) 등이 있다.

길이 $N$인 문자열 $A$가 있다. 알파벳, 수, 알파벳으로 이루어진 축약어가 쿼리로 주어질 때, 이와 매칭되는 $A$의 부분문자열이 몇 개 있는지 출력하여라. 개수를 셀 때는 같은 문자열이더라도 $A$에서의 위치가 다르면 다른 것으로 친다.

어떤 문자열의 부분문자열이란, 문자열의 양 끝에서 문자를 0ドル$개 이상 지워서 만들 수 있는 문자열을 뜻한다. 예를 들어, abc의 부분문자열은 a, b, c, ab, bc, abc로 6ドル$개가 있다.

입력

첫 번째 줄에 알파벳 소문자로만 이루어진 길이가 $N$인 문자열 $A$가 주어진다. (1ドル\le N\le 100,000円$)

다음 줄에 쿼리의 수 $Q$가 주어진다. (1ドル\le Q\le 100,000円$)

그다음 $Q$개의 줄에 축약어가 문자, 수, 문자 형태로 공백 없이 주어진다. 이때 두 문자는 알파벳 소문자이며, 가운데 수는 1ドル$ 이상 $N-2$ 이하이다.

출력

$Q$개의 줄에 쿼리의 답을 차례로 출력한다.

제한

힌트