Problem A
Planks

Tom is accumulating planks of wood to be used when chasing after Jerry the mouse. Each plank $\mathbf{p}$ has a weight $\mathbf{W_p}$ and a length $\mathbf{L_p}$, both positive integers. When Tom wants to chase after Jerry, he pulls out 2 planks, one at a time, with a target length $\mathbf{X}$. The 2 planks are never recovered after the chase.

Let the 2 planks that Tom pulls out be plank $\mathbf{A}$ first, then plank $\mathbf{B}$.

$\mathbf{A}$ is the longest plank that does not exceed the target length $\mathbf{X}$. If there is more than one such plank, a plank with the lightest weight among them is pulled out.

$\mathbf{B}$ is the shortest plank that is greater than or equal to the target length $\mathbf{X}$. If there is more than one such plank, a plank with the heaviest weight among them is pulled out.

Tom holds plank $\mathbf{A}$ in his left hand and plank $\mathbf{B}$ in his right hand. The effort $\mathbf{E}$ Tom requires for that chase is 1 plus the sum of the 2 planks’ weights multiplied by 1 plus the absolute difference in the 2 planks’ lengths, i.e. $\mathbf{E} = (1 + \mathbf{W_A} + \mathbf{W_B}) \times [1 + abs(\mathbf{L_A} - \mathbf{L_B})]$.

As Tom accumulates planks and chases Jerry, help Tom keep track of the planks and the effort required for each pull. There are 2 possible operations:

1. $\mathbf{a}$ $\mathbf{W_p}$ $\mathbf{L_p}$ : Add a new plank $\mathbf{p}$ with weight $\mathbf{W_p}$ and length $\mathbf{L_p}$.

2. $\mathbf{c}$ $\mathbf{X}$ : Tom chases Jerry, pulling out 2 planks one at a time (as described above) with target length $\mathbf{X}$. Compute and print the effort $\mathbf{E}$ Tom requires.

For each chase ($\mathbf{c}$ $\mathbf{X}$) operation, it is guaranteed that at that point, Tom can find two such planks $\mathbf{A}$ and then $\mathbf{B}$.

Input

The first line contains $\mathbf{Q}$ ($1 \le \mathbf{Q} \le 300,000$) the number of operations to perform.

Each of the next $\mathbf{Q}$ lines contains one of the 2 operations described above. Each $\mathbf{W_p}$, $\mathbf{L_p}$, $\mathbf{X}$ is a positive integer ($1 \le \mathbf{W_p} < 10,000$, $1 \le \mathbf{L_p}, \mathbf{X} < 10^{9}$).

Output

One line for each $\mathbf{c}$ $\mathbf{X}$ operation. Each line contains the effort $\mathbf{E}$ that Tom requires for that chase.

13
a 5 1
a 3 2
a 4 7
a 4 1
a 8 7
a 3 2
a 2 1
a 4 2
c 2
c 2
c 6
a 3 3
c 2

8
72
49
24