Event Log Query on Student Enrollment

Professor X from T University teaches basic C++ every year. During the course change period at the beginning of each term, students enroll through three stages: preliminary selection, formal selection, and adjustment (add/drop). The adjustment phase is the busiest. During this phase, two types of events occur:

• A student with name \(S\) enrolls in his class; his name is added to the enrollment list (it can appear multiple times if more than one student with the same name enrolls).
• A student with name \(S\) drops the course; one occurrence of \(S\) is removed from the enrollment list. It is guaranteed that before a drop event, there is at least one occurrence of \(S\) in the list.

In addition, Professor X occasionally issues queries in the following format:

Find the earliest event after which the number of students whose names have prefix S exceeds \(v\).

Here, all actions (enroll, drop, query) are recorded as events with indices starting from 1. Notice that query events do not affect the enrollment list; they only ask for a historical moment when a given condition was met.

Note:

1. If there are \(p\) enrollments with the same name, then the name appears \(p\) times in the list.
2. Only students who have enrolled can drop the course.
3. Even if a query event appears before the condition is met in real time, the query is answered by looking at the entire event log.
</p>

Your task is to, given the entire event log, answer each query by outputting the smallest event number \(i\) (1-indexed) such that immediately after processing event \(i\) the condition (the number of enrolled students whose name starts with \(S\) is greater than \(v\)) holds. If the condition is never met, output -1.

inputFormat

The input begins with an integer \(n\) representing the total number of events. The following \(n\) lines each represent one event in chronological order. Each event is in one of the following formats:

• + S: A student with name S enrolls in the course.
• - S: A student with name S drops the course.
• ? S v: A query asking for the smallest event index after which the number of enrolled students whose names start with S is greater than v. Here, v is a non-negative integer.

outputFormat

For each query event (lines that start with ?) in the order they appear in the input, output a single integer on a separate line indicating the earliest event index after which the condition is met. If the condition is never met, output -1.

sample

5
+ Alice
+ Albert
? Al 1
- Alice
? Al 1

2
2

</p>