← 返回题目列表

AtCoder · fft_c

C. furie変换

中文机器翻译题面 查看原题

問題文

本题供课程使用。页面底部提供了解释。

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 街道。