問題文
本题供课程使用。页面底部提供了解释。
AtCoder自助餐厅正在考虑推出套餐菜单。
- 主菜标价 i 日元一 A_i 有不同的类型 (1 ≦ i ≦ N)。
- 配菜价格为 i 日元一 B_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) 。
- 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 街道。