問題文

この問題は、講座用問題です。ページ下部に解説が掲載されています。

AtCoder 食堂では、定食のメニューを検討しています。

• 主菜は、価格が $i$ 円のものが $A_i$ 種類あります $(1 ≦ i ≦ N)$。
• 副菜は、価格が $i$ 円のものが $B_i$ 種類あります $(1 ≦ i ≦ N)$。

定食は、主菜と副菜を 1 種類ずつ選んで構成します。 定食の価格は、選んだ主菜と副菜の価格の和とします。

各 $k (1 ≦ k ≦ 2N)$ について、価格が $k$ 円になる定食の種類の数を計算して下さい。

入力

入力は以下の形式で標準入力から与えられる。

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

• $1$ 行目には、整数 $N (1 ≦ N ≦ 100,000)$ が書かれている。
• $2$ 行目からの $N$ 行の $i$ 行目には、整数 $A_i, B_i (0 ≦ A_i, B_i ≦ 100)$ が書かれている。

出力

$2N$ 行の出力をせよ。$k$ 行目に価格が $k$ 円になる定食の種類数を整数で出力せよ。

解説

高速フーリエ変換 from AtCoder Inc.

入力例1

4
1 1
2 2
3 4
4 8

出力例1

0
1
4
11
26
36
40
32

• $1$ 円になる組合せは存在しない。
• $2$ 円の組み合わせは、$1$ 円の主菜と副菜が $1$ 種類ずつなので $1$ 通り。
• $3$ 円の組み合わせは、$1×2 + 2×1 = 4$ 通り。