题目描述

黑板上写有 $N$ 个整数。定义 $A_k$ 和 $B_k$ 如下。

• $A_k$：进行 $k$ 次如下操作：从黑板上任选两个数，将它们擦掉，并把两数的乘积写回黑板。$A_k$ 是完成 $k$ 次操作后，黑板上所有数之和的期望。
• $B_k$：进行 $k$ 次如下操作：从黑板上任选两个数，将它们擦掉，并把两数的和写回黑板。$B_k$ 是完成 $k$ 次操作后，黑板上所有数之积的期望。

每次选择两个数时，当前黑板上所有无序数对被选中的概率相同；各次随机选择按上述规则独立进行。

求

和

对 $998244353$ 取模后的结果。

$998244353=119\times 2^{23}+1$，且它是一个质数。

输入格式

第一行包含一个整数 $N$。

第二行包含黑板上的 $N$ 个整数。每个数都满足

输出格式

第一行输出

对 $998244353$ 取模后的结果，相邻数字用空格分隔。

第二行输出

对 $998244353$ 取模后的结果，相邻数字用空格分隔。

样例

输入

3
3 6 9

输出

18 39 162
162 66 18

关于有理数取模

若一个有理数写成既约分数 $a/b$，则它模质数 $p$ 的值定义为满足

的整数 $c\in[0,p)$。

当 $b$ 不是 $p$ 的倍数时，这个 $c$ 唯一存在。

可以证明，对于本题所有合法输入，所有 $A_k$ 和 $B_k$ 都是有理数，并且写成既约分数后，分母都不是 $998244353$ 的倍数。