1166 : String Set

Description

Alice needs to help Bob maintain a set of strings. The set is empty initially and Bob may give the following instructions:

• I s: Insert the string s to the set.
• D s: Delete all strings that contain a specific substring s in the set.
• Q s: Query the number of strings that contain a specific substring s.

Input

There is only one test case.

The first line contains an integer n (1 ≤ n ≤ 50000), denoting the number of instructions. Each of the next n lines describes an instruction which consists of an instruction type and a string s. The string s consists of lowercase letters and the length of it does not exceed 1000.

The total number of insertion instructions does not exceed 10000. The total length of inserted strings is less than 700000. There will be no insertion of strings that already exist in the set. The total number of deletion instructions does not exceed 1000.

Output

For each query, output the number of strings containing a specific substring s in the set.

Sample

6
I hunan
I hncpc
Q hn
Q h
D n
Q h

1
2
0

Hint

Source

Author

Staginner