在线游戏

题目描述

有一个注册玩家数为 $N$ 的在线游戏。

今天是游戏运营以来的第 $10^{100}$ 天，开发者高桥调查了用户的登录记录。结果显示，第 $i$ 个玩家从第 $A_i$ 天开始的连续 $B_i$ 天登录了游戏，其他天没有登录。其中第 $1$ 天是运营开始日。

也就是说，第 $i$ 个玩家在第 $A_i$、$A_i+1$、$\ldots$、$A_i+B_i-1$ 天登录，且仅在这些天登录。

对于每个整数 $k$（$1 \le k \le N$），求出恰好有 $k$ 个玩家登录的天数。

输入格式

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

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

输出格式

按以下格式输出 $N$ 个整数，用空格分隔：

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

其中 $D_k$ 表示恰好有 $k$ 个玩家登录的天数。

样例

3
1 2
2 3
3 1

2 2 0

第 $1$ 个玩家在第 $1$、$2$ 天登录，第 $2$ 个玩家在第 $2$、$3$、$4$ 天登录，第 $3$ 个玩家仅在第 $3$ 天登录。

因此，第 $1$、$4$ 天有 $1$ 个玩家登录，第 $2$、$3$ 天有 $2$ 个玩家登录，其他天没有玩家登录。

答案如下：恰好有 $1$ 个玩家登录的天数为 $2$，恰好有 $2$ 个玩家登录的天数为 $2$，恰好有 $3$ 个玩家登录的天数为 $0$。

2
1000000000 1000000000
1000000000 1000000000

0 1000000000

可能存在两个或更多玩家在同一时期登录。

数据范围

• $1 \le N \le 2\times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le B_i \le 10^9$
• 输入均为整数。