#2555. SubString

内存限制:512 MiB 时间限制:30 Sec

题目描述

懒得写背景了,给你一个字符串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

样例输出


			
0

数据范围与提示