You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

桌子上有 $n$ 个玻璃杯，其中第 $i$ 个杯子的容量为 $a_i$ ，初始装有 $b_i$ 单位的水。[丛雨]经常将一个杯子里的水倒到另一个杯子里面。当这个过程进行时，会有一半的水不小心倒在地上被浪费掉，另外一半成功倒到另一个杯子里。需要注意的是，一个杯子里的水不能在任何时刻超过它的容量。具体来说，假设第 $i$ 个杯子里当前装有 $c_i$ 单位的水，将第 $i$ 个杯子之中的 $x$ 单位的水倒到第 $j$ 个杯子里面，那么第 $i$ 个杯子里将剩下 $c_i-x$ 单位的水，第 $j$ 个杯子里将会有 $min\{a_j,c_j+x/2\}$ 单位的水。丛雨有一个问题，如果将所有杯子里的水都倒到任选的 $k$ 个杯子里面去，那么这 $k$ 个杯子里最多有多少水？请你对 $1,2,3...n$ 中所有的 $k$ 求出这个答案。并保留一位小数输出结果。

输入格式（glass.in）

一行一个整数 $n$ 表示桌子上玻璃杯的个数。 接下来 $n$ 行，每行两个整数，第 $i$ 行为 $a_i, b_i$ ，分别表示玻璃杯的容量和初始水量。

输出格式（glass.out）

一行 $n$ 个实数，第 $i$ 行表示保留 $i$ 个杯子时的答案。保留一位小数。

输入样例

3
6 5
6 5
10 2

输出样例

7.0 11.0 12.0

数据范围

对于 $20\%$ 的数据，满足对于所有的 $i$ 有 $a_i = b_i$ 。 对于再 $20\%$ 的数据，满足 $n \le 20$ 。 对于再 $20\%$ 的数据，满足每个答案都是整数（当然在输出的时候是需要保留一位小数的）。 对于 $100$% 的数据，满足 $n \le 50 ，0 \le b_i \le a_i \le 100$ 。