A11509. Substrings in a String

Given a string $s$ , process $q$ queries, each having one of the following forms:

- $1ic$ — Change the $i$ -th character in the string to $c$ .
- $2lry$ — Consider the substring of $s$ starting at position $l$ and ending at position $r$ . Output the number of times $y$ occurs as a substring in it.

The first line of the input contains the string $s$ ( $1<=|s|<=10^{5}$ ) of lowercase English letters.

The second line contains an integer $q$ ( $1<=q<=10^{5}$ ) — the number of queries to process.

The next $q$ lines describe the queries and may have one of the following forms:

- $1ic$ ( $1<=i<=|s|$ )
- $2lry$ ( $1<=l<=r<=|s|$ )

$c$ is a lowercase English letter and $y$ is a non-empty string consisting of only lowercase English letters.

The sum of $|y|$ over all queries of second type is at most $10^{5}$ .

It is guaranteed that there is at least one query of second type.

All strings are $1$ -indexed.

$|s|$ is the length of the string $s$ .

For each query of type $2$ , output the required answer in a separate line.

Consider the first sample case. Initially, the string aba occurs $3$ times in the range $[1,7]$ . Note that two occurrences may overlap.

After the update, the string becomes ababcbaba and now aba occurs only once in the range $[1,7]$ .