You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

USACO 2008 January Gold

题目描述

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终，FJ 决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实，FJ 决定将湖的横截面建成 $N(1\le N\le 100,000)$ 个连续的平台高低错落的组合状，所有的平台从左到右按 $1\sim N$ 依次编号。当然咯，在湖中注入水后，这些平台都将被淹没。平台 $i$ 在设计图上用它的宽度 $W_i(1\le W_i\le1,000)$ 和高度（你可以理解为该平台顶离 FJ 挖的地基的高度）$H_i(1\le H_i\le 1,000,000)$ 来描述的。所有平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张 FJ 的设计图：

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

按 FJ 的设想，在坑挖好后，他会以 $1$ 单位每分钟的速度往最低的那个平台上注水。水在离开水管后立即下落，直到撞到平台顶或是更早些时候注入的水。然后，与所有常温下的水一样，它会迅速地流动、扩散。简单起见，你可以认为这些都是在瞬间完成的。FJ 想知道，对于每一个平台，它的顶部是从哪个时刻开始，与水面的距离至少为 $1$ 单位长度。

WATER              WATER OVERFLOWS                     
       |                       |                           
     * |          *      *     |      *      *            *
     * V          *      *     V      *      *            *
     *            *      *    ....    *      *~~~~~~~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~** :    *      *~~~~**~~~~~~*
     *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
     *    *********      *~~~~*********      *~~~~*********
     *~~~~*********      *~~~~*********      *~~~~*********
     **************      **************      **************
     **************      **************      **************
     After 4 mins        After 26 mins       After 50 mins

     Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged

输入格式

第一行一个正整数 $N$。

下面 $N$ 行，每行两个正整数 $W_i,H_i$。

输出格式

$N$ 行，每行一个正整数，表示：对于每一个平台，它的顶部是从哪个时刻开始，与水面的距离至少为 $1$ 单位长度。

3
4 2
2 7
6 4

4
50
26