Professor X is a teacher at T University who teaches basic C++ to many students every year. At T University, every student must register for courses before the start of each semester. Course registration is divided into three stages: pre-registration, formal registration, and add/drop. The "add/drop" stage is the busiest.

During the add/drop stage, students can either add or drop courses. For Professor X, the following two types of events can occur during this stage: 1. A student named $S$ adds his course (the name $S$ will appear in Professor X's list of enrolled students). 2. A student named $S$ drops his course (the name $S$ will be removed from Professor X's list of enrolled students).

At the same time, Professor X is very concerned about which students have enrolled in his course, so he queries the list of enrolled students from time to time. The format of each query is as follows: After which event was the number of students whose names have $S$ as a prefix first greater than $v$?

Professor X thinks you have extraordinary talent, so he wants to test you with this problem. You are certainly not afraid and have bravely accepted this task.

Note 1: Student names may be identical. If $p$ students with the same name have all enrolled in Professor X's course, their names will appear on Professor X's list $p$ times. Note 2: Only students who have already enrolled in the course can drop it. If a student named $S$ drops the course, the name $S$ must have been on Professor X's list before they dropped it. Note 3: Adding a course, dropping a course, and querying are all defined as "events". Event numbering starts from 1.

Input

The first line contains a positive integer $n$, representing the total number of events that occurred.

The next $n$ lines each describe an event. The first positive integer $k$ in each line indicates the event type: 1. If $k=1$, it represents an "add course" event. It is followed by a string $S$, indicating that a student named $S$ has added Professor X's course. 2. If $k=2$, it represents a "drop course" event. It is followed by a string $S$, indicating that a student named $S$ has dropped Professor X's course. 3. If $k=3$, it represents a "query" event. It is followed by a string $S$ and three non-negative integers $a, b, c$. Professor X wants to know the earliest event index after which the number of students whose names have $S$ as a prefix exceeded $(a \cdot |ANS| + b) \pmod c$. $|ANS|$ represents the absolute value of the answer to the previous query event. If it is the first query, $|ANS|=0$. If the value never exceeded the threshold at any time, the answer is $-1$.

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

Output

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

Examples

Input 1

8
1 john
1 tom
3 to 0 1 10
1 tom
3 to 0 2 10
2 tom
3 to 0 2 10
3 to 0 3 10

Output 1

2
4
4
-1

Note