На доске записано $N$ целых чисел. Определим $A_k$ и $B_k$ следующим образом:

• $A_k$: Мы $k$ раз выполняем операцию: выбираем любые два числа на доске, стираем их и записываем на доску их произведение. $A_k$ — это математическое ожидание суммы всех чисел, оставшихся на доске.
• $B_k$: Мы $k$ раз выполняем операцию: выбираем любые два числа на доске, стираем их и записываем на доску их сумму. $B_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

Выходные данные 2

162 66 18

Примечание

Если рациональное число представлено в виде несократимой дроби $\frac{a}{b}$, то остаток от деления этого числа на простое число $p$ — это такое целое число $c$ ($0 \le c < p$), которое удовлетворяет сравнению $a \equiv c \cdot b \pmod{p}$. Если $b$ не делится на $p$, то такое значение $c$ единственно.

В этой задаче можно доказать, что для всех возможных входных данных $A_0, \dots, A_{N-1}$ и $B_0, \dots, B_{N-1}$ являются рациональными числами, и при представлении каждого из них в виде несократимой дроби знаменатель не делится на $998\,244\,353$.