J. Journey through time
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Noronha loves games and time travel, therefore, he created a game where you have to answer queries about the present and also about the past! He is a professional in this game and decided to play with you. Given a set initially empty, you must do one of the following operations:

  1. Add an element $$$x$$$ to the set;
  2. Say the biggest element in the set after operation $$$t$$$;
  3. Say the smallest element in the set after operation $$$t$$$;
  4. Say the sum of the elements in the set after operation $$$t$$$.

Since you are smart (and lazy), you decided to write a program that plays the game for you.

Input

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the total number of operations.

The next $$$n$$$ lines describe the operations made. Each one of these lines represents an operation as follows

  • "1 $$$x$$$" you have to add the element $$$x$$$ $$$(1 \leq x \leq 10^9)$$$ to the set;
  • "2 $$$t$$$" you must say the biggest element in the set after operation $$$t$$$ $$$(1 \leq t \leq n-1)$$$;
  • "3 $$$t$$$" you must say the smallest element in the set after operation $$$t$$$ $$$(1 \leq t \leq n-1)$$$;
  • "4 $$$t$$$" you must say the sum of the elements in the set after operation $$$t$$$ $$$(1 \leq t \leq n-1)$$$.
It is guaranteed that $$$t$$$ is smaller or equal to the number of operations made until now and that the first operation is of type 1.
Output

For each operation of type $$$2$$$,$$$3$$$ or $$$4$$$, print the the operation's answer.

Examples
Input
7
1 10
2 1
2 2
3 2
4 2
1 5
2 6
Output
10
10
10
10
10
Input
2
1 3
4 1
Output
3
Input
6
1 1
1 10
2 2
3 3
4 4
4 1
Output
10
1
11
1