Description

You are given a string init. You need to support three operations:

1. Insert several characters at the end of the current string.

2. Delete several characters from the end of the current string.

3. Ask how many times a string $s$ appears in the current string (as a consecutive substring).

You must support these operations online.

Input Format

The first line contains an integer $q$, the number of operations.

The second line contains a string, the initial string init.

Then follow $q$ lines, each containing two strings Type Str.

If Type is ADD, it means inserting at the end.

If Type is DEL, it means deleting from the end.

If Type is QUERY, it means asking how many times a certain string appears in the current string.

To reflect online operations, you need to maintain a variable mask, whose initial value is $0$.

After reading the string Str, use the following process to decode it into the real queried string TrueStr.

When querying, query TrueStr and output one line with the answer Result.

Then update mask = mask xor Result.

When inserting, just append TrueStr to the end of the current string.

Output Format

For each operation of type $3$, output one line with an integer representing the answer.

3
A
QUERY B
ADD BBABBBBAAB
DEL 1

0

Hint

Constraints: the total length of the string changes and the initial length satisfy $\le 8 \times 10^5$. The number of queries is $\le 10^5$. The total length of all query strings is $\le 3 \times 10^6$.

The character set is uppercase letters. Note that the strings in ADD and QUERY operations both need to be decompressed.

Translated by ChatGPT 5