Description

I have broken many girls' hearts into pieces. But none of them mad at me. None.

~ by anonymous surgeon

You're a surgeon, you need to mend those girls' hearts. Therefore you need a data structure to support some functions.

This question is about maintain a set that contains only integers.

There will be n instructions.

Each instruction will be either:

insert:

Insert a new element ai into the set. Note that if the element has already in the set, do nothing.

 

print:

print all the element in the set in increasing order.

 

min:

print the number in the set that is the smallest. If there's no number, do nothing.

 

range_erase:

You will have two integer l, r.

You need to erase all the elements ai in the set that l <= ai <= r

Hint: You can solve this question very fast by using std::set .

These are some functions you may use in your code:

set.begin(), set.size(), set.erase(), set.lower_bound(), set.upper_bound(), set.insert(). To traverse through your set, you may also need iterator or type auto(only in c++11!)

You can also solve this question in C.

 

 

 

 

Input

the input will contain several lines.

The first line only contains an integer n (1 <= n <= 5000)

The following are n lines.

Each lines contains a instruction list above.

Note that ai (0 <= ai <= 10^9)

Output

 

For each print instruction, print all the number in the set in increasing order.

Each number is separated by a single blank.(No blank at the the end!)

Remember to print \n at the end of output

 

For each min instruction, print the smallest number in the set.

Remember to print \n at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please maintain a minmax-heap, which stores integers and is able to support following operations:

(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.

(2) POPMIN – Delete the minimum element from the heap. Do nothing if no elements in heap.

(3) POPMAX – Delete the maximum element from the heap. Do nothing if no elements in heap.

(4) MIN– Print the minimum element in the heap.

(5) MAX– Print the maximum element in the heap.

(5) CLEAR– Delete all elements in the heap.

Hint : std::multiset

Input

There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 500000 at any time.

Output

For each “MIN/MAX” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

set:

Sets are containers that store unique elements following a specific order.

#include <set>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

insert: Insert element

erase: Erase elements

find: Get iterator to element

 

list:

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

#include <list>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

front: Access first element

back: Access last element

emplace_front: Construct and insert element at beginning

emplace_back: Construct and insert element at the end

push_front: Insert element at beginning

push_back: Insert element at the end

pop_front: Delete first element 

pop_back: Delete last element

 

vector:

Vectors are sequence containers representing arrays that can change in size.

#include <vector>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

front: Access first element

back: Access last element

emplace_back: Construct and insert element at the end

push_back: Add element at the end

pop_back: Delete last element

 

queue:

#include <queue>

empty: Test whether container is empty

size: Return container size

push: Insert element

pop: remove next element

front: Access next element

 

stack:

#include <stack>

empty: Test whether container is empty

size: Return container size

top: Access next element

push: Insert element

pop: remove next element

 

map:

#include <map>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

insert: Insert Element

erase: Erase element

count : Count elements with a specific key

find: Get iterator to element

operator[]: Access element

 

deque:

#include <deque>

push_front: Insert element at beginning

push_back: Insert element at the end

pop_front: Delete first element 

pop_back: Delete last element

empty: Test whether container is empty

size: Return container size

insert: Insert element

erase: Erase element

operator []: Access element

front: Access first element

back: Access last element

clear: Clear the container

 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss