Artificial Lake#10154

Artificial Lake

1 second

128 megabytes

Hard

The oppressively hot summer days have driven the cows' clamoring to an all-time high. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of $n$ soon-to-be-submerged levels, conveniently numbered $1 \dots n$ from left to right.

Each level $i$ is described by two integers: its width $w_{i} (1 \leq w_{i} \leq 1000$ w_i~(1 \le w_i \le 1000) and its height (representing its relative elevation) $h_{i} (1 \leq h_{i} \leq 1 0^{6})$ h_i~(1 \le h_i \le 10^6). The heights of FJ's levels are all distinct. An infinitely tall barrier encloses the lake model on both the left and right. One example of a lake profile is shown below.

         *             *  :
         *             *  :
         *             *  8
         *    ***      *  7
         *    ***      *  6
         *    ***      *  5
         *    **********  4 <- height
         *    **********  3
         ***************  2
         ***************  1
Level    |  1 |2|  3   |

In FJ's model, he begins filling the lake at sunrise by flowing water into the lowest elevation at a rate of one square unit per minute. The water falls vertically until it hits a surface, after which it flows and spreads as water naturally would. As in all good models, assume that both falling and flowing occur instantaneously.

Determine the time at which each level becomes submerged by a layer of water of height $1$ .

WATER              WATER OVERFLOWS                     
       |                       |                           
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************

     After 4 mins        After 26 mins       After 50 mins
     Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged

Warning: The answer will not always fit in a $32$ -bit integer.

Input

The first line contains one integer $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Each of the next $n$ lines describes level $i$ with two integers $w_{i}$ w_i and $h_{i}$ h_i.

Output

Print $n$ lines. Line $i (1 \leq i \leq n)$ i~(1 \le i \le n) contains one integer representing the number of minutes after sunrise at which level $i$ becomes covered by water of height $1$ .

Examples

Example 1