Given a string of length n,
Bobo is going to perform q operations of the following 2 kinds:

1. to change the i-th character of the string (i.e. ) into c;
2. to query how many times does p occur as substring of s.
That is, count the number of indices i such that and .

Find out the result of each opeartion of the second kind.

输入描述:

The input contains at most 10 sets. For each set:

The first line contains 2 integers n, q
().

The second line contains a string  of lowercase characters.

The i-th of the last q lines may:
1. contains an integer  and a lowercase character ,
which denote an operation to change the  into 
().
2. contains an 0 followed by a string  of lowercase characters,
which denote an operation to query the number of times that  occurs as a substring ().

输出描述:

For each operation of second kind in each set,
an integer denotes the number of substrings.

5 5
aaaaa
0 aa
2 b
0 aba
4 b
0 aba

4
1
2

1 1
a
0 a

1