题目描述

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 $positions$ ，其中 $positions[i] = [left_i, sideLength_i]$ 表示：第 $i$ 个方块边长为 $sideLength_i$ ，其左侧边与 x 轴上坐标点 $left_i$ 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。

返回一个整数数组 $ans$ ，其中 $ans[i]$ 表示在第 $i$ 块方块掉落后堆叠的最高高度。

输入格式

第一行一个整数 $n$，表示方块的数量。

接下来 $n$ 行， 每行两个空格分隔的数，分别表示这个方块左侧边与 x 轴上坐标点 $left_i$ 和方块边长为$sideLength_i$ 。

输出格式

一行 $n$ 个 空格分隔的数表示在第 $i$ 块方块掉落后堆叠的最高高度。

样例

样例 1：

3
1 2
2 3
6 1

2 5 5

解释： 第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。

第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。

第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。

样例 2：

2
100 100
200 100

100 100

解释： 第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。

第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。

注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。

数据规模

• $1 <= positions.length <= 1000$
• $1 <= left_i <= 10^8$
• $1 <= sideLength_i <= 10^6$