问题陈述

这个问题是一个课堂上的问题。解析已经在页面底部显示了。

AtCoder 食堂正在考虑定食的菜单。

• 主菜有 $A_i$ 种，每种的价格为 $i$ 日元，其中 $i$ 的取值范围为 $(1 ≦ i ≦ N)$。
• 副菜有 $B_i$ 种，每种的价格为 $i$ 日元，其中 $i$ 的取值范围为 $(1 ≦ i ≦ N)$。

定食由一种主菜和一种副菜组成。定食的价格是所选主菜和副菜价格的总和。

对于每个 $k (1 ≦ k ≦ 2N)$，请计算价格为 $k$ 日元的定食种类的数量。

输入

从标准输入读入输入数据，输入格式如下：

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

• 第 $1$ 行包含整数 $N (1 ≦ N ≦ 100,000)$。
• 接下来的 $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$ 日元的主菜和副菜各一种。
• 价格为 $3$ 日元的组合有 $4$ 种，即 $1\times2 + 2\times1 = 4$ 种。