Il y a $N$ entiers écrits sur un tableau. Définissons $A_k$ et $B_k$ comme suit :

• $A_k$ : On effectue $k$ fois l'opération consistant à choisir deux nombres quelconques sur le tableau, à les effacer et à écrire leur produit sur le tableau. $A_k$ est l'espérance de la somme de tous les nombres inscrits sur le tableau après ces opérations.
• $B_k$ : On effectue $k$ fois l'opération consistant à choisir deux nombres quelconques sur le tableau, à les effacer et à écrire leur somme sur le tableau. $B_k$ est l'espérance du produit de tous les nombres inscrits sur le tableau après ces opérations.

Lors du choix aléatoire de deux nombres, toutes les paires ont la même probabilité d'être sélectionnées, et toutes les opérations sont indépendantes.

Calculez $A_0, \dots, A_{N-1}$ et $B_0, \dots, B_{N-1}$ modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ est un nombre premier.

Entrée

La première ligne contient $N$ ($1 \le N \le 200\,000$). La deuxième ligne contient les $N$ entiers inscrits sur le tableau, séparés par des espaces. Chaque nombre est supérieur ou égal à $0$ et inférieur à $998\,244\,353$.

Sortie

La première ligne doit contenir $A_0, \dots, A_{N-1}$ modulo $998\,244\,353$, séparés par des espaces. La deuxième ligne doit contenir $B_0, \dots, B_{N-1}$ modulo $998\,244\,353$, séparés par des espaces.

Exemples

Entrée 1

3
3 6 9

Sortie 1

18 39 162
162 66 18

Remarque

Lorsqu'un nombre rationnel est représenté sous forme de fraction irréductible $\frac{a}{b}$, son reste modulo un nombre premier $p$ est l'unique entier $c$ tel que $0 \le c < p$ et $a \equiv c \cdot b \pmod{p}$, à condition que $b$ ne soit pas un multiple de $p$.

Dans ce problème, on peut démontrer que pour toutes les entrées possibles, $A_0, \dots, A_{N-1}$ et $B_0, \dots, B_{N-1}$ sont des nombres rationnels et que, lorsque chaque nombre est représenté sous forme de fraction irréductible, le dénominateur n'est pas un multiple de $998\,244\,353$.