Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 102400/131072 K (Java/Others)


Given a string S. K-string is the sub-string of S and it appear in the S at least K times.It means there are at least K different pairs (i,j) so that Si,Si+1... Sj equal to this K-string. Given m operator or query:1.add a letter to the end of S; 2.query how many different K-string currently.For each query ,count the number of different K-string currently.


The input consists of multiple test cases.
Each test case begins with a line containing three integers n, m and K(1<=n,K<=50000,1<=m<=200000), denoting the length of string S, the number of operator or question and the least number of occurrences of K-string in the S.
The second line consists string S,which only contains lowercase letters.
The next m lines describe the operator or query.The description of the operator looks as two space-separated integers t c (t = 1; c is lowercase letter).The description of the query looks as one integer t (t = 2).


For each query print an integer — the number of different K-string currently.

Sample Input

3 5 2 abc 2 1 a 2 1 a 2

Sample Output

0 1 1




2013 Multi-University Training Contest 4