黒板に $N$ 個の整数が書かれている。$A_k$ と $B_k$ を以下のように定義する。

• $A_k$: 黒板から任意の2つの数を選んで消し、その2数の積を黒板に書くという操作を $k$ 回行う。このとき、黒板に書かれている数の合計の期待値。
• $B_k$: 黒板から任意の2つの数を選んで消し、その2数の和を黒板に書くという操作を $k$ 回行う。このとき、黒板に書かれている数の積の期待値。

任意の2数を選ぶ際、すべてのペアが選択される確率は等しく、すべての試行は独立である。

$A_0, \dots, A_{N-1}$ と $B_0, \dots, B_{N-1}$ を $998\,244\,353\,(= 119 \times 2^{23} + 1)$ で割った余りを求めよ。$998\,244\,353$ は素数である。

入力

1行目に $N$ が与えられる。($1 \le N \le 200\,000$)

2行目に黒板に書かれた $N$ 個の整数が空白区切りで与えられる。各数は $0$ 以上 $998\,244\,353$ 未満である。

出力

1行目に $A_0, \dots, A_{N-1}$ を $998\,244\,353$ で割った余りを空白区切りで出力する。

2行目に $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$ の倍数ではないことが証明できる。