Another ICPC String Problem

You are given a string $s$ of length $n$. Process $q$ queries of the following $2$ types:

1. Change the $i$-th character of the string (i.e. $s_i$) into $c$;

2. 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\le i\le n-m+1$ and $s_i{s}_{i+1}\dots ,s_{i+m-1}=p_1{p}_2\dots p_m$.

Find the result of each query of type 2.

Giriş verilənləri

The first line of the input contains $2$ integers $n,q$ ($1\le n\le 5\times 10^4,1\le q\le 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:

1. If it's a query of the first type, it will contain an integer $k_i$ ($1\le k_i\le n$) and a lowercase character $c_i$, which means that character $s_{k_i}$ becomes $c_i$

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

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

Çıxış verilənləri

For each operation of type $2$ output the number of times that the query string appears as a substring of $s$.

Nümunələr