题目描述

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

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

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

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

输入格式

• 第 $1$ 行：$1$ 个整数 $n$

• 第 $2\sim n+1$ 行：第 $i+1$ 行为 $2$ 个用空格隔开的整数 $w_i$、$h_i$，描述了第 $i$ 个平台

输出格式

• 第 $1\sim n$ 行：第 $i$ 行为 $1$ 个整数，表示平台 $i$ 的顶到水面的距离从何时开始大于 $1$ 单位长度

3
4 2
2 7
6 4

4
50
26

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq w_i\leq 1000$，$1\leq h_i\leq 10^6$

提示

输入对应了题目中给出的例子，一共有 $3$ 个平台，FJ 选定的注水点在最低的 $1$ 号平台上方。

$4$ 分钟后平台 $1$ 被淹没。$26$ 分钟后平台 $3$ 被淹没。$50$ 分钟后平台 $2$ 被淹没。

题目来源

Usaco2008 Jan Gold