配点 : $400$ 点

問題文

あるオンラインゲームがあり、 $N$ 人のプレイヤーが登録しています。 サービス開始日から $10^{100}$ 日を迎えた今日、 開発者である高橋君がログイン履歴を調べたところ、 $i$ 番目のプレイヤーはサービス開始日を $1$ 日目として、 $A_i$ 日目から $B_i$ 日間連続でログインし、 それ以外の日はログインしていなかったことが判明しました。 すなわち、$i$ 番目のプレイヤーはサービス開始日から、$A_i$ , $A_i+1$ , $\ldots$ , $A_i+B_i-1$ 日目に、 かつそれらの日にのみログインしていたことが分かりました。 $1\leq k\leq N$ をみたす各整数 $k$ について、 サービス開始日から今日までの間で、ちょうど $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$ はちょうど $i$ 人がゲームにログインしていた日数を表す。

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

$2$ 人以上のプレイヤーがちょうど同じ期間にログインしていることもあり得ます。