Description

wxh太强了，他觉得你们太菜了，所以懒得写背景了，给你一个字符串init，要求你支持三个操作

(1):在当前字符串的后面插入若干个字符

(2):在当前字符串的后面删除若干个字符

(3):询问字符串s在当前字符串中出现了几次？(作为连续子串)

你必须在线支持这些操作。

Format

Input

第一行一个数Q表示操作个数

第二行一个字符串表示初始字符串init

接下来Q行，每行2个字符串Type,Str

Type是ADD的话表示在后面插入。

Type是DEL的话表示在后面删除。

Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作，你需要维护一个变量mask，初始值为0

读入串Str之后，使用这个过程将之解码成真正询问的串TrueStr。

询问的时候，对TrueStr询问后输出一行答案Result

然后mask = mask xor Result

插入的时候，将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压

字符集大写字母

数据字符串变化长度以及初始长度和 <= 800000，询问次数 <= 100000,询问总长度 <= 3000000

Output

Samples

3
A
QUERY B
ADD BBABBBBAAB
DEL 1

0