Dynamic Median Finder

You are given a sequence of operations to perform on a dataset. Each operation is provided as a line of text. There are two types of operations:

• add X: Insert the number X into the dataset.
• median: Calculate and output the median of all numbers currently in the dataset.

If the dataset is empty and the median is requested, output Empty.

The median is defined as follows.

For a sorted sequence \(a_1, a_2, \ldots, a_n\):

\[ \text{median} = \begin{cases} a_{\frac{n+1}{2}}, & \text{if } n \text{ is odd},\\ \frac{a_{\frac{n}{2}} + a_{\frac{n}{2}+1}}{2}, & \text{if } n \text{ is even}. \end{cases} \]

Process the operations until the line end is reached. Note that the end command is only used to denote the end of input and should not be processed as an operation.

inputFormat

Input is given from standard input. Each line contains a command which is one of the following:

• add X where X is an integer.
• median which indicates that you should compute the median of the current dataset.
• end indicating the end of input. This line should not be processed.

The commands are given one per line.

outputFormat

For each median command, output the current median on a new line. If the dataset is empty when median is requested, output Empty.

## sample

median
end

Empty

</p>