UOJ Logo Universal Online Judge

UOJ

附件下载 统计

English Problem Statement

跳蚤国智能电网的建设正在如火如荼地进行,而负责工程的伏特需要一批优秀的工程师来协助工作。为了考察新入职工程师的水平,伏特设计了一个关于电阻匹配的测试题。

测试装置由 n 条彼此并联的电线组成,每条电线上都有一个灯泡。现在,有 2n 个电阻,每个电阻都有一个固定的电阻值 a1a2n。工程师的任务是将这些电阻分配到电线中,使每条电线上恰好有两个电阻,并计算每条电线的等效电阻(等效电阻等于两个电阻的电阻值之和)。

对于每种可能的匹配方案,可以计算 n 条电线的等效电阻并将它们从小到大排序。设排序后第 i 亮的灯泡对应的电线(也就是等效电阻第 i 小的电线)等效电阻为 bi,对于每个 i{1,2,,n},伏特希望知道所有可能的匹配方案下,bi 的总和是多少。答案需要对 998244353 取模。

两个匹配方案不同,当且仅当存在至少一个电阻(在两个方案中)匹配到的电阻不同。容易发现一共有 (2n)!n!2n 个不同的匹配方案。

你能通过这个测试,证明自己具备优秀的工程能力吗?

输入格式

第一行,一个整数,表示 n

第二行,2n 个整数 a1a2n

输出格式

一行,n 个整数,依次表示每个 i 的答案。

样例一

input

2
3 1 4 2

output

12 18

explanation

  • 1 种匹配方案:{a1+a2,a3+a4}。等效电阻排序前为:[4,6],排序后为:[4,6]
  • 2 种匹配方案:{a1+a3,a2+a4}。等效电阻排序前为:[7,3],排序后为:[3,7]
  • 3 种匹配方案:{a1+a4,a2+a3}。等效电阻排序前为:[5,5],排序后为:[5,5]
  • 所有可能的匹配方案下,b1 的总和 =4+3+5=12
  • 所有可能的匹配方案下,b2 的总和 =6+7+5=18​。

样例二

input

3
1 1 1 1 2 2

output

30 42 48

样例三 ~ 七

见下发文件。

限制与约定

对于 100% 的数据,1n4001ai108

子任务编号 n 子任务分值
1 8 10
2 15 15
3 30 20
4 100 25
5 400 30

时间限制:4s

空间限制:1GB