You are given a string $S$ of length $N$ consisting of only lower case English alphabets. You will need to answer $Q$ queries of the following types.

• $1 \ L \ R \ W$: Find the number of occurrences of string $W$ in substring $[L,R]$ of string $S$.
• $1 \ L \ R \ U$: Update the substring $[L,R]$ of string $S$ with string $U$.

Input format

• The first line contains two space-separated integers $N$ and $Q$.
• The second line contains a string $S$ of length $N$.
• Next $Q$ lines contains queries of two types as given in the problem statement.

Output format

For each query of $type \ 1$: 

• You are required to print the number of occurrences of string $W$ in substring $[L,R]$ of string $S$ in a new line.

Constraints

$1\le N\le 10^5$

$1\le L\le R\le N$

$|W|\le min(R-L+1,10)$

$|U|=R-L+1$

$\sum_{i=1}^{Q} |W|\le 10^6$

$\sum_{i=1}^{Q} |U|\le 10^5$