Xsquare thinks that the Mathematics and Computer Science are closely related to each other. Today, he has learnt about the Central Measure of Tendencies i.e Mean , Mode and Median in his mathematics class .

MEAN

The mean is equal to the sum of all the values in the data set divided by the number of values in the data set. So, if we have n values in a data set and they have values x₁, x₂, ..., x_n, the sample mean, usually denoted by (pronounced x bar), is:

MODE

The mode is the most frequent score in our data set. On a histogram it represents the highest bar in a bar chart or histogram. You can, therefore, sometimes consider the mode as being the most popular option. An example of a mode is presented below:

NOTE :

If there are more than one possible candidates for the MODE. Choose the smallest one.

MEDIAN

The median is the middle score for a set of data that has been arranged in order of magnitude.

For eg :

Consider the following set of elements .

We first need to rearrange that data into order of magnitude (smallest first):

Our median mark is the middle mark - in this case, 56 (highlighted in bold).

If even number of elements are present in the set. Then, we have to take the middle two scores and average the result.

We again rearrange that data into order of magnitude (smallest first):

Only now we have to take the 5th and 6th score in our data set and average them to get a median of 55.5.

Xsquare thinks of implementing a data structure which can implements following functions very efficiently .

• Insert X  : Insert an element X into the set.
• Delete X : Delete an element X from the set. It is guaranteed that such X always exist in the data structure.
• Mean     : Report Mean of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.
• Mode     : Report Mode of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.
• Median  : Report Median of the elements present in the data set. It is guaranteed that data structure will not be empty at this query.

Input

First line of input contains a single integer Q denoting the number of operations. Each of the next Q lines of input defines any of the above mentioned operation.

Output

For each operation of type Mean , Mode , Median, print only the integer part of the answer.

Constraints

1 <= Q <= 5 * 10⁵

1 <= X <= 10⁹