Dual Priority Queue

A dual priority queue is a data structure that supports inserting and deleting data, just like an ordinary priority queue. The difference from an ordinary priority queue is that, on a delete operation, it removes either the element with the highest priority or the one with the lowest priority, depending on the command.

A dual priority queue supports two kinds of operations: one inserts data, and the other deletes data. The delete operation is further split into two: one removes the element with the highest priority, and the other removes the element with the lowest priority.

Suppose we have a dual priority queue $Q$ that stores only integers. Treat the value of each integer stored in $Q$ as its priority.

Given a sequence of operations to apply to $Q$, write a program that processes all of them and then prints the maximum and minimum values among the data remaining in $Q$.

Input is read from standard input. The input consists of $T$ test cases.

The first line contains the number of test cases $T$. The first line of each test case contains an integer $k$ ($k \le 10^6$), the number of operations to apply to $Q$. Each of the following $k$ lines contains a character (I or D) denoting an operation and an integer $n$.

• I n: insert the integer $n$ into $Q$. The same integer may be inserted more than once.
• D 1: delete one occurrence of the maximum value in $Q$.
• D -1: delete one occurrence of the minimum value in $Q$.

If the maximum (or minimum) value occurs more than once, only one of them is deleted. If a D operation is applied while $Q$ is empty, that operation is ignored. Every integer stored in $Q$ is at least $-2^{31}$ and less than $2^{31}$.

Output is written to standard output. For each test case, after processing all operations, print the maximum and minimum among the values remaining in $Q$ on a single line, separated by a single space. If $Q$ is empty, print EMPTY.