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

• $1 *i* *c*$ — Change the $*i*$-th character in the string to $*c*$.
• $2 *l* *r* *y*$ — 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.

Input

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:

• $1 *i* *c*$ ($1 ≤ *i* ≤ |*s*|$)
• $2 *l* *r* *y*$ ($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*$.

Output

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

Note

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]$.