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

• $A_k$：在黑板上任选两个数擦除，并将它们的乘积写回黑板，重复此操作 $k$ 次。此时，黑板上所有数的和的期望值。
• $B_k$：在黑板上任选两个数擦除，并将它们的和写回黑板，重复此操作 $k$ 次。此时，黑板上所有数的积的期望值。

每次任选两个数时，每对数被选中的概率相等，且所有操作相互独立。

求 $A_0, \dots, A_{N-1}$ 和 $B_0, \dots, B_{N-1}$ 对 $998\,244\,353$ ($= 119 \times 2^{23} + 1$) 取模后的结果。$998\,244\,353$ 是一个质数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 200\,000$)。

第二行包含 $N$ 个整数，表示黑板上写的数，以空格分隔。每个数均在 $0$ 到 $998\,244\,353$ 之间（含 $0$）。

输出格式

第一行输出 $A_0, \dots, A_{N-1}$ 对 $998\,244\,353$ 取模后的结果，以空格分隔。

第二行输出 $B_0, \dots, B_{N-1}$ 对 $998\,244\,353$ 取模后的结果，以空格分隔。

样例

输入格式 1

3
3 6 9

输出格式 1

18 39 162
162 66 18

说明

当有理数表示为最简分数 $\frac{a}{b}$ 时，该数对质数 $p$ 取模的结果定义为满足 $a \equiv c \cdot b \pmod{p}$ 的唯一整数 $c$ ($0 \le c < p$)，前提是 $b$ 不是 $p$ 的倍数。

在本题中，可以证明对于所有可能的输入，$A_0, \dots, A_{N-1}$ 和 $B_0, \dots, B_{N-1}$ 均为有理数，且将其表示为最简分数时，分母均不是 $998\,244\,353$ 的倍数。