Problem A
Buff! Buff! Buff!

You are currently playing a card game with your friend. In this game, there are $10^9$ types of cards, and each card has its own power. In each turn, you either add a card to your hand, compare the strongest card you have in your hand against the one in your friend’s hand, or “buff” the cards in your hand. Here, the buff may increase or decrease the power of the cards currently in your hand (yes, the buff may turn out to be a debuff!). There are two kinds of buff: one that affects each card in your hand, and one that only affect each card of a certain type in your hand.

You are playing for $Q$ turns. In each turn, exactly one of these action occur:

• You add a card of type $T$ with power $P$ to your hand.

• You buff each card in your hand by $B$. In other words, you add $B$ to the power of each card in your hand.

• You buff each card of type $T$ in your hand by $B$. In other words you add $B$ to the power of each card of type $T$ in your hand.

• You want to compare the strongest card in your hand against the one in your friend’s hand. Hence, you need to find the power of the strongest card you have at the moment.

Enough talking, let the game begin!

Input

The first line contains one integer $Q$ ($1 \le Q \le 200\; 000$), denoting the number of turns.

The next $Q$ lines will be in the form of one of the following:

• $\texttt{ADD}\; T\; P$ ($1 \le T \le 10^9$, $-10^8 \le P \le 10^8$), meaning you add a card of type $T$ with power $P$ to your hand.

• $\texttt{BUFF_ALL}\; B$ ($-10\; 000 \le B \le 10\; 000$), meaning you add $B$ to the power of each card in your hand.

• $\texttt{BUFF}\; T\; B$ ($1 \le T \le 10^9$, $-10\; 000 \le B \le 10\; 000$), meaning you add $B$ to the power of each card of type $T$ in your hand.

• $\texttt{MAX}$, meaning you have to output the power of the strongest card in your hand. It is guaranteed that there is at least one card in your hand.

Output

For each “$\texttt{MAX}$” action, output the power of the strongest card in your hand.

Subtasks

1. ($14$ Points): Only contains the following input:

                   10
                   ADD 1 10
                   ADD 2 5
                   MAX
                   BUFF_ALL -3
                   MAX
                   BUFF 2 7
                   MAX
                   ADD 2 6
                   BUFF 1 1
                   MAX
           

2. ($18$ Points): $Q \le 2\; 000$.

3. ($13$ Points): There is no $\texttt{BUFF_ALL}$ and $\texttt{BUFF}$ action.

4. ($15$ Points): There is no $\texttt{BUFF}$ action.

5. ($20$ Points): There is no $\texttt{BUFF_ALL}$ action, and $P, B > 0$ for each action.

6. ($10$ Points): $P, B > 0$ for each action.

7. ($10$ Points): No additional constraints.

Explanation of Sample 1

The following is the state of your hand after the first 2 actions.

The power of the strongest card is $10$. Then, after doing “$\texttt{BUFF_ALL}\; 5$”, the state of your hand is the following.

The power of the strongest card is $15$. After doing “$\texttt{BUFF}\; 1\; -6$”, the state of your hand changes into the following.

The power of the strongest card is $12$. Finally, after doing “$\texttt{ADD}\; 1\; 777$”, the state of your hand turns into the following.

And the power of the strongest card is $777$.

Explanation of Sample 2

After the first action, the state of your hand is the following.

The power of the strongest card is $-7$. Then, after doing “$\texttt{ADD}\; 1\; -10$”, the state of your hand is the following.

The power of the strongest card is $-7$. Finally, after doing “$\texttt{ADD}\; 2\; 9$”, the state of your hand turns into the following.

Where the power of the strongest card is $9$.

Warning

The I/O files are large. Please use fast I/O methods.

9
ADD 1 10
ADD 2 7
MAX
BUFF_ALL 5
MAX
BUFF 1 -6
MAX
ADD 1 777
MAX

10
15
12
777

6
ADD 1 -7
MAX
ADD 1 -10
MAX
ADD 2 9
MAX

-7
-7
9

8
BUFF_ALL 5
ADD 77777777 77
MAX
ADD 12345678 2
BUFF 12345678 775
MAX
BUFF 77777777 7700
MAX

77
777
7777