Problem Statement

"Bus" (bus) is an abbreviation of "omnibus" (omnibus).

In this spirit, for a string $X$ of length at least $3$ consisting of lowercase English letters, we call the string formed by taking the last $3$ characters of $X$ the abbreviation of $X$.

You are given a string $S$ of length $N$ whose $i$-th character is $S_i$. Process $Q$ queries in order.

Each query is of one of the following types.

• Type $1$ 1 k x : Change $S_k$ to the character $x$.
• Type $2$ 2 l r a : Let $T$ be the string formed by taking the $l$-th through $r$-th characters of $S$. Output the number of (contiguous) substrings of $T$ of length at least $3$ whose abbreviation equals $a$.

Here, substrings taken from different positions are counted separately, even if they are equal as strings.

Input

$N\ Q$
$S$
$query_1$
$query_2$
$\vdots$
$query_Q$

• $3\leq N\leq 2\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• $N, Q$ are integers.

Here, $query_i (1\leq i\leq Q)$ is the $i$-th query, given in one of the following formats.

$1\ k\ x$

• $k$ is an integer satisfying $1\leq k\leq N$.
• $x$ is a lowercase English letter.

$2\ l\ r\ a$

• $1\leq l\leq r\leq N$
• $a$ is a string of length $3$ consisting of lowercase English letters.
• $l, r$ are integers.

Output

Output the answers to the type $2$ queries in order. On the $k$-th line, output the answer to the $k$-th type $2$ query. Note that it is not guaranteed that at least $1$ type $2$ query is given.
Print a newline at the end.

Sample

14 5
ambushbusiness
2 1 5 bus
2 1 12 bus
1 3 x
2 1 12 bus
2 3 10 usi

3
10
7
6