黑板上寫著 $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$。

輸出格式

第一行輸出 $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}$ 的 $0$ 以上且小於 $p$ 的整數 $c$。若 $b$ 不是 $p$ 的倍數，則此值唯一。

在本題中，可以證明對於所有可能的輸入，$A_0, \dots, A_{N-1}$ 與 $B_0, \dots, B_{N-1}$ 皆為有理數，且當各數表示為既約分數時，分母皆不是 $998\,244\,353$ 的倍數。