Description

X is a teacher at University T. Every year, he teaches many students basic C++ knowledge. At University T, before the start of each semester, every student needs to choose courses. Each course selection process has three stages: pre-selection, main selection, and add/drop; among them, the “add/drop” stage is the busiest.

During the add/drop stage, students can either add a course or drop a course. For Teacher X, the following two types of events may happen during the add/drop stage:

1. A student with name $S$ adds his course (the name will appear in X’s list of enrolled students).
2. A student with name $S$ drops his course (the name will be removed from X’s list of enrolled students).

At the same time, Teacher X cares a lot about which students have enrolled in his course, so he will query the enrolled-student list from time to time. For each query, he asks: after which event, as early as possible, does the number of students whose names have prefix $S$ become greater than $v$.

Teacher X thinks you are talented, so he wants to test you with this problem. You are not afraid, so you bravely take on the task.

Note 1: Student names may be the same. If there are $p$ students with the same name who have all enrolled in Teacher X’s course, then their name will appear $p$ times in Teacher X’s list.

Note 2: Only students who have already enrolled can drop the course. If a student with name $S$ drops the course, then before dropping, Teacher X’s list must contain that name.

Note 3: Adding, dropping, and querying are all defined as “events”, and event indices start from $1$.

Input Format

The first line contains a positive integer $n$, indicating that a total of $n$ events occur.

In the next $n$ lines, each line describes an event. The first integer $k$ in each line indicates the event type:

1. If $k = 1$, it is an add-course event. Next comes a string $S$, meaning that a student with name $S$ adds Teacher X’s course.
2. If $k = 2$, it is a drop-course event. Next comes a string $S$, meaning that a student with name $S$ drops Teacher X’s course.
3. If $k = 3$, it is a query event. Next comes a string $S$ and three non-negative integers $a, b, c$, meaning that Teacher X wants to know after which event, as early as possible, the number of students whose names have prefix $S$ becomes greater than $(a*|ANS|+b) \bmod c$. $|ANS|$ denotes the absolute value of the answer to the previous query event. If this is the first query, then $ANS=0$. If this value is never exceeded at any time, then the answer is $-1$.

Note: All strings in the input contain only lowercase letters.

Output Format

For each query event, output one line containing the answer to that query.

8
1 jead
1 dec
3 de 0 0 10
1 dec
3 de 0 1 10
2 dec
3 de 0 1 10
3 de 0 2 10

2
4
4
-1

Hint

$n \le 10^5, |S| \le 60$. All strings in the input contain only the first $10$ lowercase letters.

Translated by ChatGPT 5