C - 高速フーリエ変換 Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

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

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 円になる定食の種類数を整数で出力せよ。

解説

入力例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 通り。