You are given a string $s$ of length $n$. Process $q$ queries of the following $2$ types: \begin{enumerate} \item Change the $i$-th character of the string (i.e. $s_i$) into $c$; \item Answer the query: how many times does $p$ occur as a substring of $s$? That is, count the number of indices $i$ such that $1 \leq i \leq n - m + 1$ and $s_{i} s_{i + 1} \dots, s_{i + m - 1} = p_1 p_2 \dots p_m$. \end{enumerate} Find the result of each query of type 2. \InputFile The first line of the input contains $2$ integers $n, q$ ($1 \leq n \leq 5\times 10^4, 1 \leq q \leq 10^5$). The second line of the input contains a string $s$ of length $n$ consisting of lowercase Latin characters. $q$ lines follow, which may have one of the following formats: \begin{enumerate} \item If it's a query of the first type, it will contain an integer $k_i$ ($1 \leq k_i \leq n$) and a lowercase character $c_i$, which means that character $s_{k_i}$ becomes $c_i$ \item If it's a query of the second type, it will contain a $0$ followed by a nonempty string $p$ of lowercase characters, meaning that you should find the number of times that $p$ occurs as a substring of $s$. \end{enumerate} It is guaranteed that there is at least one query of type $2$. It is guaranteed that the sum of lengths of strings $p$ over all queries of the type $2$ doesn't exceed $5\cdot 10^4$. \OutputFile For each operation of type $2$ output the number of times that the query string appears as a substring of $s$.