RAM

Hackers broke into Mirko's computer through the Shellshock vulnerability and raised the system voltage, destroying almost all of its RAM except the last 2MB. Mirko's computer has exactly 26 hard disks, labeled with the uppercase English letters A to Z. Fortunately, Mirko has a huge log of hard disk accesses. The log is a string of hard disk labels in the order the disks were accessed.

Mirko analyzed the attack as follows:

• He split the log into $N$ smaller files $S_1, S_2, \ldots, S_N$ that fit in RAM. Each file is a string of uppercase English letters, and concatenating the files in order gives the whole log.
• He loaded the files one after another. Right after loading file $S_i$, he counted how many times hard disk $H_i$ was accessed among the last $K_i$ accesses of the log from its beginning up to and including file $S_i$.

Write a program that answers all $N$ of Mirko's queries.

The first line contains the number of files $N$ ($1 \le N \le 200\,000$).

The next $2N$ lines are divided into $N$ groups of two lines. The $i$-th group is:

• The first line contains a string $S_i$ of uppercase English letters ($1 \le |S_i| \le 4\,000$).
• The second line contains an uppercase English letter $H_i$, the label of a hard disk, and the number of accesses $K_i$, separated by a space ($1 \le K_i \le \sum_{j=1}^{i} |S_j|$).

The total length of all files, $\sum_{i=1}^{N} |S_i|$, is at most $2\,000\,000$.

Print $N$ lines with the answers to Mirko's queries in order. Line $i$ contains the exact number of characters equal to $H_i$ among the last $K_i$ characters of the concatenation of $S_1$ through $S_i$.