问题描述

有 $10^{100}$ 个方块排成一排。这些方块从左到右依次编号为 $1$ 到 $10^{100}$。

我们有 $N$ 个编号为 $1$ 到 $N$ 的棋子，以及一个计数器，可以存储 $0$ 到 $10^{100}$ 之间的整数（包括边界值）。

我们将使用这些工具进行 $N$ 个过程。初始时，所有的方块都是白色的。第 $i$ 个（$i≥ 1$）过程如下：

1. 将棋子 $i$ 放在方块 $S_i$ 上，并将计数器置为 0。
2. 查看棋子 $i$ 放置的方块的颜色。如果方块是白色的，则将其涂成黑色，并将计数器增加 1。否则（如果方块是黑色的），将棋子 $i$ 向右移动一格。因此，一个方块可能包含多个棋子。
3. 如果计数器的值等于 $C_i$，则终止该过程。否则，返回步骤 2。

找出所有 $N$ 个棋子在完成 $N$ 个过程后的最终位置。

输入

输入以以下格式从标准输入给出：

$N$ $S_1$ $C_1$ $S_2$ $C_2$ : $S_N$ $C_N$

• 第一行包含一个整数 $N$（$1 ≦ N ≦ 10^5$）。
• 接下来的 $N$ 行描述了各个过程。其中第 $i$ 行（$1 ≦ i ≦ N$）包含两个用空格分隔的整数 $S_i$（$1 ≦ S_i ≦ 10^9$）和 $C_i$（$1≦C_i≦10^9$），分别表示第 $i$ 个过程中棋子的初始位置和该过程的终止条件。

部分分

在此问题中，可以获得部分分数：

• 通过满足以下条件的测试集可获得 35 分：每个过程结束后，每个棋子所在的方块编号不超过 $10^5$。
• 通过满足 $N ≦ 1000$ 的测试集可获得另外 40 分。
• 通过无附加限制的测试集可获得另外 25 分。

输出

输出 $N$ 行，其中第 $i$ 行（$1≦i≦N$）应该包含第 $i$ 个过程结束后棋子 $i$ 所在的方块编号。请确保输出末尾有换行符。

示例输入 1

4
3 3
10 1
4 2
2 4

示例输出 1

5
10
7
11

以下是每个过程后方块和棋子的状态示意图：

示例输入 2

8
2 1
3 1
1 1
5 1
1 1
9 1
8 2
7 9

示例输出 2

2
3
1
5
4
9
10
18

示例输入 3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

示例输出 3

1999999999
2999999999
3999999999
4999999999
5999999999

请注意，正确的输出可能不适合 $32$ 位整数。