题目描述

有一个在线游戏，注册了 $N$ 个玩家。
今天是游戏发布之后的第 $10^{100}$ 天，开发者高桥检查了用户的登录记录。结果发现第 $i$ 个玩家从第 $A_i$ 天开始连续登录了 $B_i$ 天，其中第 $1$ 天是发布日，其它天没有登录。换句话说，第 $i$ 个玩家在第 $A_i$ 天、$A_i+1$ 天、$\\ldots$、$A_i+B_i-1$ 天登录，只有这些天登录。
对于每个整数 $k$，$1\\leq k\\leq N$，找出刚好有 $k$ 个玩家登录的天数。

约束条件

• $1 \\leq N \\leq 2\\times 10^5$
• $1 \\leq A_i \\leq 10^9$
• $1 \\leq B_i \\leq 10^9$
• 输入中的所有值都是整数。

输入

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

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_N$ $B_N$

输出

以空格分隔打印 $N$ 个整数，如下所示：

$D_1$ $D_2$ $\\cdots$ $D_N$

这里，$D_i$ 表示刚好有 $k$ 个玩家登录的天数。

示例输入 1

3
1 2
2 3
3 1

示例输出 1

2 2 0

第一个玩家在第 $1$ 天、$2$ 天登录，第二个玩家在第 $2$ 天、$3$ 天、$4$ 天登录，第三个玩家只在第 $3$ 天登录。

因此，我们可以看到第 $1$ 天、$4$ 天有 $1$ 个玩家登录，第 $2$ 天、$3$ 天有 $2$ 个玩家登录，其它天没有玩家登录。

答案是：刚好有 $1$ 个玩家登录的天数有 $2$ 天，刚好有 $2$ 个玩家登录的天数有 $2$ 天，刚好有 $3$ 个玩家登录的天数有 $0$ 天。

示例输入 2

2
1000000000 1000000000
1000000000 1000000000

示例输出 2

0 1000000000

可能有两个或更多的玩家在同一段时间登录。