AT_fft_c 高速フーリエ変換

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/fft_c 本题为讲座用题目，页面下方附有题解。 AtCoder 食堂正在考虑定食的菜单。 - 主菜中，价格为 $i$ 日元的有 $A_i$ 种类（$1 \leq i \leq N$）。 - 副菜中，价格为 $i$ 日元的有 $B_i$ 种类（$1 \leq i \leq N$）。 定食由一种主菜和一种副菜组成。定食的价格为所选主菜和副菜价格之和。 请计算对于每个 $k\ (1 \leq k \leq 2N)$，价格为 $k$ 日元的定食有多少种。

输入以以下格式从标准输入读入。 > $N$ > $A_1\ B_1$ > $A_2\ B_2$ > $\vdots$ > $A_N\ B_N$ - 第 $1$ 行包含一个整数 $N\ (1 \leq N \leq 100,\!000)$。 - 接下来的 $N$ 行，第 $i$ 行包含两个整数 $A_i,\ B_i\ (0 \leq A_i,\ B_i \leq 100)$。

请输出 $2N$ 行。第 $k$ 行输出价格为 $k$ 日元的定食种类数。

### 题解 **[高速傅里叶变换](https://www.slideshare.net/secret/fc5RcW8Wkqciu "高速フーリエ変換")** by **[AtCoder Inc.](http://www.slideshare.net/chokudai)** ### 样例解释 1 - 价格为 $1$ 日元的组合不存在。 - 价格为 $2$ 日元的组合，由于 $1$ 日元的主菜和副菜各有 $1$ 种，所以有 $1$ 种组合。 - 价格为 $3$ 日元的组合有 $1 \times 2 + 2 \times 1 = 4$ 种。 由 ChatGPT 4.1 翻译