NIO is playing a string game with OIN. If you don't know this game, here're the rules:

OIN writes down a main string  and a set  with  strings , and NIO needs to answer the number of strings in  that are lexicographically less than  as fast as possible.

However, it is too easy for NIO to solve this problem, so OIN decides to make the problem a little more difficult. Now he has four kinds of operations:

•  , add one lowercase Latin letter  at the back of string ().

•  , erase the last  letters of string , where .

• , add  lowercase Latin letters  at the back of string ().

•  , ask the number of strings in  that is strictly lexicographically less than .

OIN will do the operations above for  times. However, it is still easy for NIO, and he thinks it is boring, so he wants you to write a program to solve it automatically.

String  is lexicographically less than string  if  and one of two following conditions is satisfied:

•   is a prefix of the string ;

• For some , the first characters of the string  are equal to the corresponding characters of the string , and .
  

The first line contains two integers  and  --- the number of strings in  and the number of operations ().

The second line contains a string  consisting of no more than  lowercase Latin letters.

The -th of the next  line contains one string , which is in the set . It is guaranteed that the total length of strings in  does not exceed .

The following  lines contain descriptions of operations.

All strings contain only lowercase Latin letters,  will never be an empty string

For each operator , output one line containing a single integer---the answer to the question.

6 11
abe
aaa
aa
aab
aac
abd
bc
4
2 1
4
3 1 d
4
3 2 a
4
2 4
4
1 3 d
4

5
4
4
5
0
0