Ali의 타자기
시간 제한1초메모리 제한512 MB
문자열을 만들어 출력하는 키 입력 열이 주어질 때, x번째 문자열이 y번째 문자열 안에 몇 번 나타나는지 묻는 질의에 답한다.
문제
Ali는 별난 기계를 모으는 걸 좋아한다. 최근에는 옛날식 타자기를 하나 손에 넣었다. 이 타자기에는 28개의 키가 있는데, 26개는 알파벳 소문자이고 나머지 2개는 대문자 'B'와 'P'이다.
자세히 살펴본 Ali는 타자기가 이렇게 동작한다는 걸 알게 된다.
- 소문자 키를 누르면 타자기는 그 글자를 특별한 홈에 덧붙인다. '
P'를 누르기 전까지는 이런 글자가 적어도 하나 있어야 한다. - '
B' 키를 누르면 타자기는 홈에 마지막으로 추가된 글자를 지운다. - '
P' 키를 누르면 타자기는 홈에 있는 모든 글자를 종이에 인쇄하고 다음 줄로 넘어간다. 홈에 있는 글자는 사라지거나 바뀌지 않는다. 이 동작을 하려면 홈에 글자가 적어도 하나 있어야 한다.
예를 들어 Ali가 aPaPBbP 키를 누르면 종이에는 이런 것들이 인쇄된다.
a
aa
ab
종이에 인쇄된 문자열에 1부터 n까지 번호를 붙인다. 이 타자기에는 아주 흥미로운 기능이 하나 있다. 숨겨진 숫자 키패드가 있어서, 두 수 (x, y)(1 ≤ x, y ≤ n)를 입력하면 타자기가 y번째 문자열 안에 x번째 문자열이 나타나는 횟수를 보여주는 것이다.
Ali는 이 기능을 발견하고 매우 신이 났다. 똑같은 기능을 하는 프로그램을 짜고 싶어 한다. 도와줄 수 있는가?
입력
첫째 줄에 Ali가 타자기에서 누르는 모든 키를 나타내는 문자열이 하나 주어진다.
둘째 줄에는 질의의 개수를 나타내는 정수 m이 하나 주어진다.
다음 m개 줄에는 숨겨진 숫자 키패드에 대한 질의가 하나씩 주어진다. 이 중 i번째 줄에는 두 정수 x와 y가 주어지며, 이는 i번째 질의가 (x, y)라는 뜻이다.
출력
m개 줄을 출력한다. i번째 줄에는 i번째 질의의 답을 나타내는 정수 하나를 출력한다.
제한
모든 테스트 케이스의 속성은 아래에 나와 있다.