问题陈述
10^{100} 方块排成一排。方块已编号 1 通过 10^{100} 从左到右。
我们有 N 件编号 1 通过 N, 和一个可以存储整数的计数器 0 和 10^{100}, 包括在内。
我们将表演 N 使用这些工具进行处理。最初,正方形被漆成白色。 i^{th} (1≦i≦N) 流程如下:
- 放置棋子 i 在广场上 S_i,并将计数器设置为 0.
- 看方块的颜色 已放置 i 。如果正方形是白色的,则将其涂成黑色并将计数器增加 1。否则(如果方块是黑色),移动棋子 i 右边一格。因此,一个正方形可能包含多个棋子。
- 如果计数器的值为 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^{th} (1 ≦ i ≦ N) 包含两个空格分隔的整数 S_i (1 ≦ S_i ≦ 10^9) 和 C_i (1≦C_i≦10^9), 表示棋子的初始位置 i 在 i^{th} 进程及终止条件 i^{th} 分别处理。
部分积分
此问题可能会获得部分分数:
- 35 分:经过所有过程后,每个棋子所在的方格数不超过 10^5.
- 另一个 通过满足以下条件的测试集将获得 40 积分 在没有额外限制的情况下通过测试集将获得 N ≦ 1000.
- 另一个 通过满足以下条件的测试集将获得 25 分。
输出
打印 N 行, i^{th} (1≦i≦N) 其中应包含棋子所在方格的编号 i 位于所有 N 进程。确保在输出末尾打印换行符。
示例输入 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位整数。