2555 - SubString

懒得写背景了，给你一个字符串init，要求你支持两个操作 (1):在当前字符串的后面插入一个字符串 (2):询问字符串s在当前字符串中出现了几次？(作为连续子串) 你必须在线支持这些操作。

输入

第一行一个数Q表示操作个数 第二行一个字符串表示初始字符串init 接下来Q行，每行2个字符串Type,Str Type是ADD的话表示在后面插入字符串。 Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。 为了体现在线操作，你需要维护一个变量mask，初始值为0

读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。 询问的时候，对TrueStr询问后输出一行答案Result 然后mask=maskxorResult 插入的时候，将TrueStr插到当前字符串后面即可。 HINT:ADD和QUERY操作的字符串都需要解压 长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000 新加数据一组--2015.05.20

输出

样例

输入

2
A
QUERY B
ADD BBABBBBAAB

输出


                


                
                            

        


                    
提示

            

                
:ADD和QUERY操作的字符串都需要解压
长度 <= 600000，询问次数<= 10000,询问总长度<= 3000000
新加数据一组--2015.05.20
Output
Sample Input
2
A
QUERY B
ADD BBABBBBAAB
Sample Output
0
Hint


            

        
            

            

        

            
            

                
                

                    时间限制
                    
                        1 秒                    
                

                

                    内存限制
                    128 MB
                

                
            

        


        

         讨论                 统计
        


         上一题
        下一题