Background

Translated from Problem K of NERC 2018.

Problem Description

Some knights want to visit the King. Since all knights here are very polite, they make an appointment in advance, specifying the time when they will arrive and how long the visit will last. The knights visit the King in the order of times recorded at the reception desk, and each knight must wait until the previous knight finishes.

Unfortunately, the Princess also wants to visit the King. However, the kind Princess will not change the knights’ visiting order. Instead, she will wait until the knights have finished their visits and then visit the King. Please compute how long the Princess has to wait.

Input Format

There are $q+1$ lines in total.

The first line contains an integer $q \ (1 \leq q \leq 3 \times 10^5)$.

Then there are $q$ lines, each starting with a character.

• If the character is +, it is followed by two numbers, meaning that knight $i$ will arrive at time $t \ (1 \leq t \leq 10^6)$, and the visit duration is $d \ (1 \leq d \leq 10^6)$ time units.

• If the character is -, it is followed by a number $i \ (1 \leq i \leq q)$, meaning that knight $i$ temporarily cancels his appointment.

• If the character is ?, it is followed by a number $t \ (1 \leq t \leq 10^6)$, meaning that the Princess will visit at time $t$.

Output Format

For each ?, output one line indicating how long the Princess has to wait. Note that, when the Princess visits, the appointment records of the knights include only the previous operations, and do not include those added later.

19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6

0
1
0
2
1
3
2
1
2
1
0
0
2
1
1

Hint

For all testdata, it is guaranteed that $1 \leq q \leq 3 \times 10^5$, $1 \leq t \leq 10^6$, and $1 \leq d \leq 10^6$.

Translated by ChatGPT 5