时间限制：1s

空间限制：256MB

Description

有 \(n\) 个编号为 \(1, \cdots, n\) 的纸箱子。其中第 \(i\) 个箱子最多可以装 \(a_i\) 个气球，目前装有 \(b_i\) 个气球。

小季想要选择 \(k\) 个箱子，并在其中拿到尽可能多的气球。为了完成这个任务，小季可以随意将气球从一个箱子拿到另一个箱子，次数不限。然而，由于小季比较笨拙，每次他试图转移任何数量的气球时，一半的气球都会掉在地上。

简单来说，假设一个箱子 \(i\) 目前含有 \(c_i\) 个气球，而一个箱子 \(j\) 含有 \(c_j\) 个气球。假设小季试图将 \(x\) 个气球从箱子 \(i\) 拿到到箱子 \(j\) （显然， \(x\) 不能超过\(c_i\)）。那么，\(x / 2\) 个气球将会掉在地上。拿完后，箱子 \(i\) 中会剩余 \(c_i - x\) 个气球，箱子 \(j\) 中会剩余 \(\min(a_j, c_j + x / 2)\) 个单位（装满气球后多余的气球也会掉出来）。

每次拿气球时，小季可以任意选择从哪个箱子 \(i\) 拿到哪个箱子 \(j\) ，同时拿气球的数量 \(x\) 可以是任意正实数。

求解对于每个 \(k = 1, \cdots, n\) ，确定在箱子之间拿气球 \(0\) 次或更多次后，任意选择的 \(k\) 个箱子所能收集的最大可能的气球总数。

Input Format

第一行包含一个整数 \(n\) - 箱子的数量。

接下来的 \(n\) 行描述了箱子。每行包含两个整数 \(a_i\) 和 \(b_i\) - 分别表示每个箱子的容量，以及箱子 \(i\) 目前所含的气球数。

Output Format

打印 \(n\) 个实数 - 分别为任选 \(k = 1, \cdots, n\) 个箱子所能收集的最大气球数。结果保留整数部分即可。

Data Range

\(1 \leq n \leq 100\) , \(0 \leq b_i \leq a_i \leq 100\)，\(a_i > 0\) 。

Input Example #1：

3
6 5
6 5
10 2

Output Example #1：

7 11 12

Note

对于样例数据，小季可以采取以下方案：

• 对于 \(k=1\) ，将气球从前两个箱子转移到第三个箱子，掉落 \((5+5)/2=5\) 个气球，第三个箱子变为 \(2 + (5+5)/2 = 7\) 个气球 。
• 对于 \(k=2\) ，将气球从第三个箱子转移到前两个箱子中的任意一个，掉落 \(2/2=1\) 个气球，前面的箱子变为 \(5 + 5 + 2/2 = 11\) 个气球 。
• 对于 \(k=3\) ，不需要移动，最终答案和为 \(5 + 5 + 2 = 12\) 个气球。