P5335 [THUSC 2016] Add/Drop Period

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$.**

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.**

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

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