题目描述

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

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

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

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

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

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

输入格式

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

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

输出格式

第${1..N}$行:

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

样例

输入样例

3
4 2
2 7
6 4

输出样例

4
50
26

提示

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

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

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

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

输入说明:

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