Bit Game Company has recently released a new game, "Magic Tower Online," where players can control a warrior to fight monsters in the game world. At the time of the game's release, there are no monsters in the Magic Tower. Subsequently, $q$ events will occur in sequence, each being one of the following three types:

• + x y z a b: Indicates that a new version of the game has been released, and a new monster has been added to the game. If this is the first monster added, its ID is $1$; otherwise, its ID is the ID of the last added monster $+1$. This monster is located on the $x$-th floor of the Magic Tower, has a level of $y$, and a difficulty of $z$. If the player chooses to kill this monster, it costs $a$ health points. After a successful kill, the player receives a potion that restores $b$ health points and uses it immediately.
• - k: Indicates that a new version of the game has been released, and the monster with ID $k$ has been removed due to balancing issues; it will no longer appear in the Magic Tower. Note: Removed monsters retain their IDs, and future added monsters will not reuse the IDs of removed monsters.
• ? g l d: Represents a query. A player wishes to kill all monsters in the first $g$ floors of the Magic Tower that have a level not exceeding $l$ and a difficulty not exceeding $d$. The player can kill these monsters in any order. Climbing to a new floor does not require killing all monsters on the current floor, and the player will not be interfered with by other monsters during the process. Your task is to help the player calculate the minimum amount of health the warrior must have before setting out. If at any point the warrior's health becomes negative, the game ends; you must prevent this from happening.

Write a program to answer each query in sequence. Note: Each query is merely a hypothetical scenario for the player and does not actually kill any monsters.

Input

The first line of the input contains an integer $q$, representing the number of events.

The next $q$ lines each start with a character, followed by several integers, describing each event in order.

The input data guarantees $1\leq q\leq 150000$, the total number of monsters does not exceed $50000$, and the number of queries does not exceed $50000$.

For the add monster operation, it is guaranteed that $1\leq x,y,z\leq 10000$ and $0\leq a,b\leq 10^9$.

For the remove monster operation, it is guaranteed that the operation is valid and each monster will not be removed more than once.

For queries, it is guaranteed that $1\leq g,l,d\leq 10000$.

Output

For each query, output a single integer on a new line, representing the minimum health required before setting out.

Examples

Input 1

10
+ 2 1 1 3 4
+ 1 2 2 2 5
? 2 2 2
+ 1 1 1 8 2
? 2 2 1
? 1 2 2
- 1
? 2 2 2
- 3
? 1 2 2

Output 1

2
7
5
5
2

Subtasks

1. (3 points) The total number of monsters does not exceed $8$, and the number of queries does not exceed $8$.
2. (7 points) The total number of monsters does not exceed $5000$, and the number of queries does not exceed $5000$.
3. (10 points) Potions do not restore health, and all monsters have a difficulty of $1$. That is, $b=0$ and $z=d=1$.
4. (17 points) $1\leq x,y,z,g,l,d\leq 5$.
5. (30 points) All monsters have a level and difficulty of $1$. That is, $y=z=l=d=1$.
6. (33 points) No additional restrictions.