Bajtowy 森林又下起了倾盆大雨。众所周知，雨后蘑菇生长得非常快。Bajtazar 是一位狂热的采蘑菇爱好者（最有经验的 Potyczki Algorytmiczne 参赛者在六年前曾遇到过他*），他绝不会错过这样的机会。他踏上了收集尽可能多蘑菇的旅程。然而这一次，他并不打算沿着小路走。他带了一架无人机，白天可以飞到任意一片林中空地，并收集那里所有的蘑菇。这需要花费他整整一天的时间。

自从我们上次见到 Bajtazar 以来，情况发生了一些变化，森林里长出了一种新的蘑菇——线性蘑菇（Agaricus linearis）。它的名字来源于这样一个事实：在给定的空地上，每晚都会长出相同数量的新蘑菇。

森林里有 $n$ 片空地。在 Bajtazar 到达的那一天，第 $i$ 片空地上有 $b_i$ 个蘑菇，并且每晚都会增加 $a_i$ 个蘑菇。在接下来的 $k$ 天里，我们的主角每天都会派无人机前往选定的空地（可能是之前已经采摘过蘑菇的空地）。请帮助 Bajtazar 确定他通过这种方式最多能收集到多少蘑菇。Bajtazar 还没有决定他要花多少时间采蘑菇。因此，你的任务是计算对于区间 $[1, n]$ 内的每一个 $k$，他能收集到的最大蘑菇数量。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示 Bajtowy 森林中的空地数量。接下来的 $n$ 行包含空地的描述。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($0 \le a_i \le 1\,000\,000, 0 \le b_i \le 10^{12}$)，分别表示第 $i$ 片空地每晚长出的蘑菇数量和初始蘑菇数量。

输出格式

你的程序应向标准输出打印 $n$ 行。第 $k$ 行应包含如果采蘑菇持续恰好 $k$ 天，Bajtazar 在最优使用无人机的情况下所能收集到的蘑菇总数。

样例

输入 1

3
5 10
16 0
5 10

输出 1

10
26
57

*注：题目“Grzyby po deszczu”可以在 http://main.edu.pl/pl/archive/pa/2010/grz 找到。