Hay $N$ números enteros escritos en una pizarra. Definamos $A_k$ y $B_k$ de la siguiente manera:

• $A_k$: Se realiza $k$ veces la operación de elegir dos números cualesquiera de la pizarra, borrarlos y escribir su producto en la pizarra. El valor es la esperanza matemática de la suma de todos los números escritos en la pizarra al finalizar.
• $B_k$: Se realiza $k$ veces la operación de elegir dos números cualesquiera de la pizarra, borrarlos y escribir su suma en la pizarra. El valor es la esperanza matemática del producto de todos los números escritos en la pizarra al finalizar.

Al elegir dos números cualesquiera, la probabilidad de seleccionar cualquier par es la misma, y todas las operaciones son independientes.

Calcula $A_0, \dots, A_{N-1}$ y $B_0, \dots, B_{N-1}$ módulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ es un número primo.

Entrada

La primera línea contiene $N$ ($1 \le N \le 200\,000$). La segunda línea contiene los $N$ números enteros escritos en la pizarra, separados por espacios. Cada número es mayor o igual a $0$ y menor que $998\,244\,353$.

Salida

La primera línea debe contener $A_0, \dots, A_{N-1}$ módulo $998\,244\,353$, separados por espacios. La segunda línea debe contener $B_0, \dots, B_{N-1}$ módulo $998\,244\,353$, separados por espacios.

Ejemplos

Entrada 1

3
3 6 9

Salida 1

18 39 162
162 66 18

Nota

Cuando un número racional se representa como una fracción irreducible $\frac{a}{b}$, el resto de este número al dividir por un primo $p$ es el entero $c$ tal que $0 \le c < p$ y $a \equiv c \cdot b \pmod{p}$. Si $b$ no es múltiplo de $p$, este valor es único.

En este problema, se puede demostrar que para todas las entradas posibles, $A_0, \dots, A_{N-1}$ y $B_0, \dots, B_{N-1}$ son números racionales y, al expresar cada número como una fracción irreducible, el denominador no es múltiplo de $998\,244\,353$.