$Elo$特别喜欢生啃鸡蛋，今天他来到了一个有很多鸡蛋的农场。

这块区域可以看成一个二维平面坐标系，一开始$Elo$站在$(0,0)$的位置上。

农场里一共$n$个鸡蛋，第$i$个鸡蛋的坐标为$(x_i,y_i)$。

因为农场里还有很多只因，为了不吓到它们，$Elo$必须遵守以下的规则行走：

1. 若$Elo$位于$(0,y)$的位置上，他可以花费1单位的时间走至$(0,y+1)$。

2. $Elo$可以在任何时刻花费$1$单位的时间从$(x,y)$走到$(x-1,y)$或$(x+1,y)$。

当$Elo$站着的位置上存在鸡蛋时，他可以立刻啃掉这个鸡蛋且不花费任何时间。

注意可能存在同一个位置上有多个鸡蛋的情况。

现在$Elo$想要知道，对于所有的$i=1\sim n$，他啃够$i$个鸡蛋所需要的最小时间是多少(啃完以后不需要回到原点)。

第一行一个整数$n(1\leq n \leq 2000)$。

接下来一共$n$行，每一行两个整数$(x_i,y_i)\ (1\leq y_i \leq 10^9,\ -10^9\leq x_i \leq 10^9)$，表示第$i$个鸡蛋的位置。

输出共$i$行，第$i$行表示$Elo$啃够$i$个鸡蛋所需要的最小时间。