Implementing a Custom Heap

Given an initially empty heap, you are asked to perform q queries. There are 3 types of queries:
  1. add x - should add x to the heap
  1. pop - should delete the root of the heap
  1. max - should print the maximum element of the heap

Input

The first line of the input contains a single integer q (1 ≀ q ≀ 10^5).
The next q lines contain queries - each on a separate line. It’s guaranteed that for all add queries the value of x does not exceed in absolute value. It’s guaranteed that all the operations are valid and there are no pop operations on an empty heap.

Output

The program should print the appropriate values for all the max queries on separate lines.

Examples

Input
Output
9 add 1 add 2 max add -3 add 4 max add -2 pop max
2 4 2
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue