Problem G
Baby Names

Kattis is having a baby! O.o. However, she does not know what to name her baby. Thankfully, her friends have many ideas, giving suggestions for both genders.

Given $\textbf{N}$ distinct baby name suggestions (each babyName string consists of only UPPERCASE alphabet characters of no more than $30$ characters) and the genderSuitability of that name (integer $\textbf{1}$ for $\textbf{male}$ or integer $\textbf{2}$ for $\textbf{female}$) and given $\textbf{Q}$ queries, tell Kattis how many baby names start with a prefix that is inside a given query interval $[\textbf{start} \ldots \textbf{end})$, where $\textbf{start} < \textbf{end}$, and both are strings.

Note: A prefix of a string $T = T_{0}T_{1} \ldots T_{n-1}$ is string $P = T_{0}T_{1} \ldots T_{m-1}$ where $m \le n$

There will be $4$ types of commands:

1. Stop: This will be indicated by a $0$. Stop your program upon encountering this.

2. Add Suggestion: This will be indicated by a starting integer $1$ followed by a string babyName and an integer genderSuitability, e.g. $1$ SIMBA $1$.

3. Remove Suggestion: This will be indicated by a starting integer $2$ followed by a string: babyName, e.g. $2$ SIMBA. The babyName is guaranteed to have already been suggested earlier.

4. Query: This will be indicated by a starting integer $3$ followed by two strings: start, end, and an integer genderSuitability. Your job is to return the number of names that is inside the interval $[\textbf{start} \ldots \textbf{end})$ subject to the following criteria.

   • If genderSuitability = $0$: report number of names for both genders

   • If genderSuitability = $1$: report number of male names

   • If genderSuitability = $2$: report number of female names

Input

Each line will be a certain command. The program terminates when it encounters $0$. There are up to $200\, 000$ babyName suggestions and $Q$ is up to $500\, 000$.

Output

Each time the $\textbf{Query}$ command is encountered, the number of suitable names should be printed.

Subtasks

1. $\textbf{(30 points)}$: $1 \le N \le 20$, $1 \le Q \le 10$, and all baby names have distinct first letters

2. $\textbf{(30 points)}$: $1 \le N \le 20\, 000$, $1 \le Q \le 20\, 000$

3. $\textbf{(40 points)}$: $1 \le N \le 200\, 000$, $1 \le Q \le 500\, 000$

1 KATTISJR 2
1 OLIVER 1
1 SIMBA 1
3 A Z 0
3 A Z 1
3 A Z 2
2 SIMBA
3 A Z 0
3 A Z 1
3 A Z 2
0

3
2
1
2
1
1