Johnny 是一个数字收藏家——他有一个装有许多数字的大相册，他通过插入新数字和删除旧数字来不断更新它。

这个相册是 Johnny 最珍贵的宝物，因此 Johnny 想要确保没有人能用不同的数字替换他的数字。为此，他为他的相册维护了一个校验和（checksum），其确定方式如下：他考虑相册中数字的所有不同的非空子集，在每个这样的子集中，他确定最小值，最后他计算这些最小值的算术平均值。由于任何数字都可能在 Johnny 的相册中出现多次，因此这些“子集”是多重集（multisets），即每个数字在任何子集中都可以出现多次（但不能超过它在整个相册中的出现次数）。当且仅当所有数字在两个多重集中的重数（multiplicity）都相同时，这两个多重集才相等。例如，一个相册 $\{1, 2, 2, 5\}$ 具有以下 11 个不同的子集：$\{1\}$、$\{1, 2\}$、$\{1, 2, 2\}$、$\{1, 2, 2, 5\}$、$\{1, 2, 5\}$、$\{1, 5\}$、$\{2\}$、$\{2, 2\}$、$\{2, 2, 5\}$、$\{2, 5\}$ 和 $\{5\}$。

不幸的是，Johnny 的相册变化非常频繁，这使得手动维护校验和变得相当繁琐。请写一个程序来帮助他：读取要应用到相册的更新次数以及这些操作的描述，在每次连续的操作后确定校验和，并将校验和输出到标准输出。

输入格式

输入的第一行包含一个正整数 $n$ ($1 \le n \le 250\,000$)，表示对相册的更新次数。

接下来的 $n$ 行每行指定一个操作，格式如下。每个更新由一个 + 或 - 符号、一个空格和一个数字 $a_i$ ($1 \le a_i \le 1\,000\,000\,000$) 组成。它们分别表示向相册中插入数字 $a_i$，以及从相册中删除一个数字 $a_i$。

你可以假设相册初始为空，之后它总是非空的，并且只有相册中存在的数字才会被删除。

输出格式

你的程序应该向输出打印恰好 $n$ 行。第 $i$ 行应该包含第 $i$ 次更新后的校验和，如 Johnny 的公式所规定。

如果对于每个校验和，其与正确值的绝对误差或相对误差不超过 $10^{-6}$，则认为答案是正确的。

样例

输入样例 1

6
+ 10
+ 13
- 10
+ 7
+ 2
+ 5

输出样例 1

10.000000000
11.000000000
13.000000000
9.000000000
5.000000000
4.200000000

输入样例 2

4
+ 1
+ 2
+ 2
+ 5

输出样例 2

1.000000000
1.333333333
1.400000000
1.727272727

说明

在样例 1 中，在完成所有插入后，相册的内容为 $\{1, 2, 2, 5\}$。此时，Johnny 考虑以下 11 个子集：$\{1\}$、$\{1, 2\}$、$\{1, 2, 2\}$、$\{1, 2, 2, 5\}$、$\{1, 2, 5\}$、$\{1, 5\}$、$\{2\}$、$\{2, 2\}$、$\{2, 2, 5\}$、$\{2, 5\}$ 和 $\{5\}$。这些子集各自的最小值分别为：$1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5$。因此，相应的校验和为 $\frac{19}{11} \approx 1.727272727$。