A. Vote
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The first major village, Zhangjia Village, has reached its once-in-a-decade election for village chief.

This year, there are two candidates for village chief: Wang Xiaochang and Liu Xiaopeng.

Each villager has their own preference level for the two candidates, represented by an integer $$$a$$$. Specifically:

  • $$$a \gt 0$$$ means the villager will vote for Xiaochang.
  • $$$a \lt 0$$$ means the villager will vote for Xiaopeng.
  • $$$a = 0$$$ means the villager may vote for either candidate.

To secure the election, both candidates can use their "money power" to sway votes. This ability can be used infinitely, and each use costs 1 yuan to increase or decrease someone's preference level by 1.

Xiao Ming, as an observer, happily recorded the highlights of the election in the $$$Q$$$ minutes leading up to it.

Specifically, from $$$Q$$$ minutes before the election to 1 minute before the election, one of the following three events occurred every minute:

  1. '1 x y': A group of $$$x$$$ villagers with a preference level of $$$y$$$ arrives at the polling station.
  2. '2 k': Wang Xiaochang repeatedly uses his money power on the villager whose preference level is closest to 0 and not currently voting for him until at least $$$k$$$ villagers are confirmed to vote for him. If at the start of the minute, there are already at least $$$k$$$ villagers voting for him, nothing is done.
  3. '3 k': Liu Xiaopeng repeatedly uses his money power on the villager whose preference level is closest to 0 and not currently voting for him until at least $$$k$$$ villagers are confirmed to vote for him. If at the start of the minute, there are already at least $$$k$$$ villagers voting for him, nothing is done.

Now, Xiao Ming has returned home and is organizing his records. Please help Xiao Ming calculate how much money each candidate spent in each minute for records of type '2' or '3'.

Input

The first line of input contains a positive integer $$$Q$$$, representing the number of records.

The next $$$Q$$$ lines each begin with an integer $$$opt$$$ ($$$1 \le opt \le 3$$$) indicating the record type.

  • For $$$opt = 1$$$, it is followed by $$$x$$$ and $$$y$$$.
  • For $$$opt = 2$$$ or $$$3$$$, it is followed by $$$k$$$.

$$$1 \le Q \le 2 \times 10^5$$$

$$$1 \le x \le 10^5$$$

$$$-10^8 \le y \le 10^8$$$

$$$k \ge 1$$$

It is guaranteed that for any record with $$$opt = 2$$$ or $$$3$$$, there are at least $$$k$$$ voters who arrived before that record.

Output

For each record with $$$opt = 2$$$ or $$$opt = 3$$$, output a single integer on a new line representing the amount of money spent.

Example
Input
6
1 10 10
1 10 -10
1 10 0
2 30
3 30
3 20
Output
120
150
0