Description

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

Format

Input

一行一个整数 n(n ≤ 50) 表示桌子上玻璃杯的个数。 接下来 n 行，每行两个整数，第 i 行为 ai, bi(0 ≤ bi ≤ ai ≤ 100, ai > 0)，分别表示玻璃杯的容量和初始水量。

Output

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

Samples

3
6 5
6 5
10 2

7.0 11.0 12.0

Limitation

对于 20% 数据，保证对于所有的 i 有 ai = bi。 对于另外 20% 数据，保证 n ≤ 20。 对于另外 20% 数据，保证每个答案都是整数（当然在输出的时候是需要保留一位小数的）。