AB

Interview

Time limit2sMemory limit1024 MB

Summary

Maintain string sets A and B with add and delete, and count ways to write a query string as a prefix of an A element joined with a suffix of a B element.

Level: Medium5 of 10
Topics: Hash map, String, Trie
Solved: No attempts yet

Problem

Write a program that handles the following queries on sets $A$ , $B$ and a string $S$ .

add A $S$ : Adds $S$ to $A$ .
delete A $S$ : Removes $S$ from $A$ .
add B $S$ : Adds $S$ to $B$ .
delete B $S$ : Removes $S$ from $B$ .
find $S$ : Prints the number of ways to form $S$ by joining a prefix of an element of $A$ with a suffix of an element of $B$ . Two ways are different if the elements differ or if the prefixes (suffixes) differ. Empty prefixes (suffixes) are not considered.

Initially, $A$ and $B$ are empty. No query adds an element that already exists or removes an element that does not exist.

Input

The first line contains the number of queries $Q$ . $1 \leq Q \leq 1\,000$

Each of the next $Q$ lines contains one query. Strings consist of lowercase English letters, and each has length between 1 and 1,000 inclusive.

There is at least one find query.

Output

Print the answer to each find query on its own line.

Examples2

Example 1

Input

7
add A aba
add A a
add A ab
add B bab
add B b
add B ab
find abab

Expected output

Example 2

Input

8
add A a
add B bcd
add A ab
add B cd
find abcd
delete A a
delete B bcd
find abcd

Expected output

4
1