D. Experiment
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A group of scientists from MEPhI is working on another experiment. They want to conduct an experiment with various charged particles.

During the experiment, the following types of events may occur:

  • $$$1$$$ $$$x$$$ $$$t$$$ – a new particle of energy $$$x$$$ and type $$$t$$$ appears.
  • $$$2$$$ $$$x$$$ $$$t$$$ – any particle of type $$$t$$$ with energy $$$x$$$ disappears. If there are no such particles, nothing changes.
  • $$$3$$$ $$$x$$$ $$$t$$$ – the energy of all particles of type $$$t$$$ increases by $$$x$$$ units.
  • $$$4$$$ – the sum of the energies of all particles is required to be output.
  • $$$5$$$ – the minimum energy among all particles is required to be output; if there are no particles, output $$$-1$$$.

The experiment may have significant implications for future work, so the scientists ask you to write a program that will verify the correctness of the results.

Input

The first line contains a single integer $$$q\, (1 \le q \le 3 \cdot 10^5)$$$ – the number of queries. Each of the following $$$q$$$ lines contains the next query in the format described above.

It is guaranteed that in each of them $$$1 \le t \le q$$$ and $$$1 \le x \le 10^9$$$, and that all numbers in the input are integers.

Output

For each query of type $$$4$$$ and $$$5$$$, output the required number on a separate line.

Examples
Input
6
2 10 2
5
1 15 1
1 17 2
3 3 1
4
Output
-1
35
Input
17
1 10 1
1 10 2
3 10 1
5
4
1 20 1
2 20 1
5
2 10 1
4
2 30 1
2 20 1
4
5
2 10 2
4
5
Output
10
30
10
30
10
10
0
-1