B. Beautiful Contest
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We have a collection of problems, called a problem set. Each problem $$$P$$$ has its difficulty $$$d(P)$$$ and beauty $$$b(P)$$$.

A contest is an ordered set of problems selected from the problem set. The beauty of a contest is the sum of individual beauties of the problems it consists of.

Let $$$(P_1, P_2, \dots, P_k)$$$ be the problems in the contest. For a contest to be valid, each problem must be roughly twice as difficult as the one immediately preceding it, formally

$$$$$$\forall i \in \{2, \dots, k\}: d(P_{i-1}) = \left\lfloor \frac{d(P_i)}{2} \right\rfloor$$$$$$

Initially, the problem set is empty. You are given $$$n$$$ operations which modify the problem set. Each of these operations is described by a single line consisting of three integers, as follows:

  • 1 d b: A problem with difficulty $$$d$$$ and beauty $$$b$$$ is added to the problem set.
  • 2 d b: A problem with difficulty $$$d$$$ and beauty $$$b$$$ is removed from the problem set. It is guaranteed that there is at least one such problem.

After each operation, output the beauty of the most beautiful valid contest using some problems (possibly all or none) from the problem set.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of operations.

Each of the following $$$n$$$ lines consists of three space-separated integers $$$t_i$$$, $$$d_i$$$, $$$b_i$$$ ($$$1 \leq t_i \leq 2$$$, $$$1 \leq d_i \leq 10^6$$$, $$$-10^{17} \leq b_i \leq 10^{17}$$$) — the operation to be made, the problem difficulty and the problem beauty, respectively.

Output

For each operation, output a single line with an integer: the beauty of the most beautiful contest given the current problem set.

Examples
Input
10
1 1 10
1 2 10
1 3 20
1 4 20
1 5 20
2 3 20
2 2 10
2 4 20
2 5 20
2 1 10
Output
10
20
30
40
40
40
20
20
10
0
Input
1
1 10 -50
Output
0