Na tablicy zapisano $N$ liczb całkowitych. Zdefiniujmy $A_k$ oraz $B_k$ w następujący sposób:

• $A_k$: Wykonujemy $k$ razy operację polegającą na wybraniu dwóch dowolnych liczb z tablicy, usunięciu ich i zapisaniu na tablicy ich iloczynu. Wartością jest wartość oczekiwana sumy wszystkich liczb zapisanych na tablicy.
• $B_k$: Wykonujemy $k$ razy operację polegającą na wybraniu dwóch dowolnych liczb z tablicy, usunięciu ich i zapisaniu na tablicy ich sumy. Wartością jest wartość oczekiwana iloczynu wszystkich liczb zapisanych na tablicy.

Przy wyborze dwóch liczb każda para jest wybierana z równym prawdopodobieństwem, a wszystkie operacje są niezależne.

Oblicz $A_0, \dots, A_{N-1}$ oraz $B_0, \dots, B_{N-1}$ modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Liczba $998\,244\,353$ jest liczbą pierwszą.

Wejście

W pierwszej linii podano $N$ ($1 \le N \le 200\,000$).

W drugiej linii podano $N$ liczb całkowitych zapisanych na tablicy, oddzielonych spacjami. Każda liczba jest nieujemna i mniejsza niż $998\,244\,353$.

Wyjście

W pierwszej linii wypisz $A_0, \dots, A_{N-1}$ modulo $998\,244\,353$, oddzielone spacjami.

W drugiej linii wypisz $B_0, \dots, B_{N-1}$ modulo $998\,244\,353$, oddzielone spacjami.

Przykład

Wejście 1

3
3 6 9

Wyjście 1

18 39 162
162 66 18

Uwagi

Jeśli liczba wymierna w postaci nieskracalnej to $\frac{a}{b}$, to jej reszta z dzielenia przez liczbę pierwszą $p$ jest zdefiniowana jako taka liczba całkowita $c$ z przedziału $[0, p-1]$, która spełnia $a \equiv c \cdot b \pmod{p}$. Jeśli $b$ nie jest wielokrotnością $p$, to taka wartość $c$ jest wyznaczona jednoznacznie.

W tym zadaniu można udowodnić, że dla wszystkich możliwych danych wejściowych $A_0, \dots, A_{N-1}$ oraz $B_0, \dots, B_{N-1}$ są liczbami wymiernymi, a po zapisaniu ich w postaci nieskracalnej, mianownik nie jest wielokrotnością $998\,244\,353$.