AT_fft_c 高速フーリエ変換

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/fft_c この問題は、講座用問題です。ページ下部に解説が掲載されています。 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 $ 円になる定食の種類数を整数で出力せよ。

### 解説 **[高速フーリエ変換](https://www.slideshare.net/secret/fc5RcW8Wkqciu "高速フーリエ変換")** from **[AtCoder Inc.](http://www.slideshare.net/chokudai)** ### Sample Explanation 1 \- $ 1 $ 円になる組合せは存在しない。 - $ 2 $ 円の組み合わせは、$ 1 $ 円の主菜と副菜が $ 1 $ 種類ずつなので $ 1 $ 通り。 - $ 3 $ 円の組み合わせは、$ 1×2\ +\ 2×1\ =\ 4 $ 通り。