It is pouring cats and dogs over Byteotian Forest again. As everyone knows, mushrooms grow very quickly after rain. Bajtazar, an avid mushroom picker (whom the most experienced participants of Potyczki Algorytmiczne met six years ago), cannot miss such an opportunity. He has set off on an expedition to collect as many mushrooms as possible. This time, however, he does not intend to walk along the paths. He has brought a drone with him, which can fly to any clearing during the day and collect all the mushrooms from it. This takes him exactly one day.

Since our last meeting with Bajtazar, things have changed a bit, and a new species of mushroom is growing in the forest – the linear mushroom (Agaricus linearis). It owes its name to the fact that the same number of new mushrooms grows on a given clearing every night.

There are $n$ clearings in the forest. On the day of Bajtazar's arrival, there are $b_i$ mushrooms in the $i$-th clearing, and every night exactly $a_i$ more mushrooms appear. For the next $k$ days, our hero will send the drone to a chosen clearing (possibly one from which he has already collected mushrooms before). Help Bajtazar determine the maximum number of mushrooms he can collect in this way. Bajtazar has not yet decided how much time he will spend mushroom picking. Your task is to determine the sought number of mushrooms for every $k$ in the range $[1, n]$.

Input

The first line of standard input contains a single integer $n$ ($1 \le n \le 1\,000\,000$), representing the number of clearings in the Byteotian Forest. The next $n$ lines contain descriptions of the clearings. The $i$-th of these lines contains two integers $a_i, b_i$ ($0 \le a_i \le 1\,000\,000$, $0 \le b_i \le 10^{12}$), representing the number of mushrooms growing each night and the initial number of mushrooms in the $i$-th clearing, respectively.

Output

Your program should print $n$ lines to standard output. The $k$-th line should contain the number of mushrooms collected by Bajtazar using the drone optimally if the mushroom picking lasts exactly $k$ days.

Examples

Input 1

3
5 10
16 0
5 10

Output 1

10
26
57