Boris 是 WWWforces 的比赛协调员，这是一个定期举办“什么？哪里？何时？”（"What? Where? When?"）比赛的在线平台。在他的生活中有两类事件：

1. 有人向 Boris 提交了一个比赛提案（一套题目）。他将这个新提案放入等待池中。
2. 组织新比赛的时间到了。由于 Boris 不记得他的等待池中提案的初始顺序，他只是随机选择一个提案，将其从等待池中移除，并用于即将到来的比赛。等待池中的每个提案被选中的概率均等，无论它已经等待了多久。

总共会有恰好 $n$ 个第一类事件和恰好 $n$ 个第二类事件。此外，对于第 $k$ 个第二类事件，在此之前至少会有 $k$ 个第一类事件。换句话说，每当协调员需要提案时，等待池中至少会有一个提案。最后，保证没有两个事件同时发生。

对于每个提案，你应该确定它在等待池中停留的期望时间。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 100\,000$）—— 每种类型事件的数量。

接下来的 $2n$ 行描述了这些事件。每行要么是 “+ $t_i$”，要么是 “- $t_i$”，分别表示在时刻 $t_i$ 发生了第一类或第二类事件。

保证所有的 $t_i$ 都是不超过 $10^9$ 的正整数，且事件将按照 $t_i$ 严格递增的顺序给出。此外，对于第 $k$ 个第二类事件，在此之前至少会有 $k$ 个第一类事件。最后，保证恰好有 $n$ 个第一类事件和 $n$ 个第二类事件。

输出格式

对于每个提案（第一类事件），输出它在等待池中停留的期望时间。如果你的答案的绝对或相对误差不超过 $10^{-6}$，则被视为正确。

形式化地，假设你的答案是 $a$，裁判的答案是 $b$。如果满足 $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$，评测程序将认为你的答案是正确的。

样例

输入样例 1

2
+ 1
+ 3
- 8
- 12

输出样例 1

9.0000000000
7.0000000000

输入样例 2

4
+ 1
- 2
+ 3
- 4
+ 5
- 6
+ 7
- 8

输出样例 2

1.0000000000
1.0000000000
1.0000000000
1.0000000000

输入样例 3

3
+ 4
+ 10
- 11
+ 16
- 20
- 100

输出样例 3

31.5000000000
25.5000000000
44.0000000000

说明

在第一个样例中，Boris 首先收到了全部两个提案，然后将它们用于两场比赛。每个提案在每场比赛中被使用的概率均为 $\frac{1}{2}$。因此，第一个提案的期望等待时间为 $(8-1) \cdot 0.5 + (12-1) \cdot 0.5 = 3.5 + 5.5 = 9$，第二个提案的期望等待时间为 $(8-3) \cdot 0.5 + (12-3) \cdot 0.5 = 2.5 + 4.5 = 7$。

在第二个样例中，每个提案几乎在提交后立即被用于举办比赛。