题目描述

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点．最终，约翰决定建一个人工湖供奶牛消暑之用．

为了使湖看起来更加真实，约翰决定将湖的横截面建成$\red{N(1≤}$$\red{N≤}$$\red{105)}$个连续的平台高低错落的组合状，所有的平台从左到右按$\red{1}$到$\red{N}$依次编号．当然咯，在湖中注入水后，这些平台都将被淹没．

平台$\red{i}$在设计图上用它的宽度$\red{wi(l≤}$$\red{wi≤}$$\red{1000)}$和高度（你可以理解为该平台顶离约翰挖的地基的高度）$\red{Hi.（}$$\red{1≤}$$\red{Hi ≤}$$\red{1000000）}$来描述的．所有平台的高度都是独一无二的．湖的边缘可以视为无限高的平台．下面给出了一张约翰的设计图：

按约翰的设想，在坑挖好后，他会以$\red{1}$单位每分钟的速度往最低的那个平台上注水．水在离开水管后立即下落，直到撞到平台顶或是更早些时候注入的水然后，与所有常 温下的水一样，它会迅速地流动、扩散．

简单起见，你可以认为这些都是在瞬间完成的．约翰想知道，对于每一个平台，它的顶部是从哪个时刻开始，与水面的距离至少为$\red{1}$单位长度．

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

输入格式

第$\red{1}$行: $\red{1}$个整数，$\red{N}$

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

输出格式

第$\red{1..N}$行:

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

样例

输入样例

3
4 2
2 7
6 4

输出样例

4
50
26

提示

输入对应了题目中给出的例子，一共有$\red{3}$个平台，约翰选定的注水点在最低的$\red{1}$号平台上方．

$\red{4}$分钟后乎台$\red{1}$被淹没．

$\red{26}$分钟后平台$\red{3}$被淹没．

$\red{50}$分钟后平台$\red{2}$被淹没．

输入说明:

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