Problem C
Tölfræði

Murray Christianson was one of the most accomplished Scottish mathematicians of the 20th century but he was mostly known for his work in combinatorics and statistics. Among his more known work is Christianson’s theorem which revolves around permutations and permutation patterns. Despite this he placed the most emphasis on statistics and data analysis. In his days there were no computers that could maintain massive data banks and work on them, and neither did Big Data exist. He did have a lot of data to work with often enough though and did all kinds of calculations by hand, for example all the royal statistics for Victoria and her suitors.

When he died in the year 1901, the same year as Victoria and right before Edward VII took up the crown, he was working on calculating all kinds of statistics regarding the new king’s suitors. Some suitors were quitting their job and new ones were being hired, and each time some change occurred he had to calculate the youngest and oldest suitor to the king along with their average age.

To show the dominance of computers in this field, you need to write a program that does Murray’s work much faster. In this problem you get the age of a person $x_i$ and whether they are quitting or being hired, denoted by R for quitting and A for being hired. For each change pring the lowest and highest age among the suitors and the average age.

Input

The input starts with a single line containing a positive integer $Q$ which denotes the number of changes that will occur. Then there are $Q$ lines, one for each change, and on line $i$ there is a single letter, A or R, along with a positive integer $x_i$.

You may assume that suitors are hired before they quit.

Output

After each change print a single line containing the lowest age, highest age and average age of the suitors at that point. If there are no suitors at that point the line should instead be -1 -1 -1. The output is considered correct if its absolute or relative error is at most $10^{-4}$. This means it doesn’t matter how many digits the answer has as long as it’s accurate enough.

Exaplanation of Sample Inputs

The first sample shows a suitor of the age $1$ being hired and thus the lowest age is $1$, highest age is $1$ and the average age is $1$. Next a suitor of age $2$ is added and then the lowest age is still $1$, the highest age is $2$ and the average $1.5$. And on it goes.

In the next sample suitors with the ages $2$, $5$ and $2$ are added. At that point the lowest age is $2$, the highest age $5$ and the average age $3$, as can be seen on the third line of the output. Then a suitor of age $2$ quits, but the lowest age doesn’t change because there is another person of age $2$ still there. At the end the second person of age $2$ quits and thus the lowest, highest and average ages all become $5$.

Scoring

The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

5
A 1
A 2
A 4
A 5
A 6

1 1 1.000000
1 2 1.500000
1 4 2.333333
1 5 3.000000
1 6 3.600000

5
A 2
A 5
A 2
R 2
R 2

2 2 2.000000
2 5 3.500000
2 5 3.000000
2 5 3.500000
5 5 5.000000

9
A 2
R 2
A 5
A 2
R 2
R 5
A 6
A 7
A 84

2 2 2.000000
-1 -1 -1
5 5 5.000000
2 5 3.500000
5 5 5.000000
-1 -1 -1
6 6 6.000000
6 7 6.500000
6 84 32.333333