P2414 [NOI2011] Ali's Typewriter

Ali likes collecting all kinds of quirky things, and he recently found an old typewriter. The typewriter has only $28$ keys, labeled with the $26$ lowercase English letters and the two letters `B` and `P`. After some study, Ali found that the typewriter works as follows: - When a lowercase letter is entered, the letter is appended to a slot in the typewriter (this letter is added to the end of the slot). - When the `B` key is pressed once, the last letter in the slot disappears. - When the `P` key is pressed once, the typewriter prints all the current letters in the slot on the paper and starts a new line, but the letters in the slot remain. For example, if Ali inputs `aPaPBbP`, the characters printed on the paper are: ``` a aa ab ``` We number the strings printed on the paper starting from $1$ up to $n$. The typewriter has a very interesting feature: it hides a numeric keypad. By entering two numbers $(x, y)$ (where $1 \leq x, y \leq n$) on the keypad, the typewriter will display how many times the $x$-th printed string appears in the $y$-th printed string. After discovering this feature, Ali became excited and wanted to write a program to achieve the same function. Can you help him?

The first line contains a string that lists all characters Ali inputs in order. The second line contains an integer $m$, the number of queries. Each of the next $m$ lines describes one query entered via the keypad. The $i$-th line contains two integers $x, y$, representing the $i$-th query $(x, y)$.

Output $m$ lines. The $i$-th line should contain one integer, the answer to the $i$-th query.

### Constraints For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$, and the length of the first line $\leq 10^5$. | Test Points | $n$ scale | $m$ scale | string length | first line length | |:-:|:-:|:-:|:-:|:-:| | $1,2$ | $1 \leq n \leq 100$ | $1 \leq m \leq 10^3$ | - | $\leq 100$ | | $3,4$ | $1 \leq n \leq 10^3$ | $1 \leq m \leq 10^4$ | single length $\leq 10^3$, total length $\leq 10^5$ | $\leq 10^5$ | | $5 \sim 7$ | $1 \leq n \leq 10^4$ | $1 \leq m \leq 10^5$ | total length $\leq 10^5$ | $\leq 10^5$ | | $8 \sim 10$ | $1 \leq n \leq 10^5$ | $1 \leq m \leq 10^5$ | - | $\leq 10^5$ | Translated by ChatGPT 5