You are given a string s of length n. Process q queries of the following 2 types:
Change the i-th character of the string (i.e. si) into c;
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≤i≤n−m+1 and sisi+1…,si+m−1=p1p2…pm.
Find the result of each query of type 2.
The first line of the input contains 2 integers n,q (1≤n≤5×104,1≤q≤105).
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:
If it's a query of the first type, it will contain an integer ki (1≤ki≤n) and a lowercase character ci, which means that character ski becomes ci
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⋅104.
For each operation of type 2 output the number of times that the query string appears as a substring of s.