410658: GYM104069 J Journey through time

J. Journey through timetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExamplesInput

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