Priority Queue Operations

You are given a series of operations to perform on a priority queue. The priority queue supports two types of queries:

• add x: Add the integer x to the priority queue.
• getKsmallest k: Retrieve the k smallest elements in non-decreasing order.
• getKlargest k: Retrieve the k largest elements in non-increasing order.

If the queue contains fewer than k elements during a query, return all of them in the required order. Note that the operations are given sequentially, and each query should operate on all numbers inserted so far.

Your task is to implement the priority queue to support these operations.

Note: All operations are provided via standard input and results for each query should be printed to standard output on a new line, in the same order the queries appear.

The problem may be solved using efficient data structures. In some languages, library functions (e.g. heaps) may be used to retrieve the smallest or largest elements efficiently.

inputFormat

The first line of the input contains a single integer n which is the number of operations to process.

The next n lines each contain an operation in one of the following formats:

• add x where x is an integer.
• getKsmallest k where k is an integer.
• getKlargest k where k is an integer.

outputFormat

For each query operation (getKsmallest or getKlargest), output a single line with the result. The result must be the space-separated list of numbers that satisfy the query in the required order. If no elements are found for a query, output an empty line.

## sample

10
add 3
add 1
add 4
add 1
add 5
getKsmallest 2
add 9
add 2
getKlargest 3
getKsmallest 10

1 1
9 5 4
1 1 2 3 4 5 9

</p>