时间限制：1秒　　内存限制：256M

---

【问题描述】

　　夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终，FJ决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实，FJ决定将湖的横截面建成 \(N\) 个连续的平台高低错落的组合状，所有的平台从左到右按 \(1..N\) 依次编号。当然咯，在湖中注入水后，这些平台都将被淹没。

　　平台 \(i\) 在设计图上用它的宽度 \(W_i\) 和高度（你可以理解为该平台顶离FJ挖的地基的高度）\(H_i\) 来描述的。所有平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张FJ的设计图：

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

　　注意：数据不保证答案全部在 32 位整型变量的范围内。

【输入格式】

　　第 1 行: 1 个整数，\(N\)。
　　第 \(2..N+1\) 行: 第 \(i+1\) 行为 2 个用空格隔开的整数 \(W_i、H_i\)，描述了第 \(i\) 个平台。

【输出格式】

　　第 \(1..N\) 行: 第 \(i\) 行为 1 个整数，表示平台 \(i\) 的顶到水面的距离从何时开始大于 1 单位长度。

【输入输出样例】

　Input

3
4 2
2 7
6 4

　Output

4
50
26

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤100,000\)，\(1≤W_i≤1000\)，\(1≤H_i≤1000000\)。

【来源】

　　Mr.he