There are $N$ integers written on a blackboard. Let us define $A_k$ and $B_k$ as follows:

• $A_k$: Perform the operation of choosing two arbitrary numbers from the blackboard, erasing them, and writing their product on the blackboard, $k$ times. The value is the expected value of the sum of all numbers written on the blackboard.
• $B_k$: Perform the operation of choosing two arbitrary numbers from the blackboard, erasing them, and writing their sum on the blackboard, $k$ times. The value is the expected value of the product of all numbers written on the blackboard.

When choosing two arbitrary numbers, every pair is chosen with equal probability, and all trials are independent.

Find $A_0, \dots, A_{N-1}$ and $B_0, \dots, B_{N-1}$ modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Note that $998\,244\,353$ is a prime number.

Input

The first line contains $N$ ($1 \le N \le 200\,000$).

The second line contains $N$ integers written on the blackboard, separated by spaces. Each number is between $0$ and $998\,244\,352$ inclusive.

Output

The first line should contain $A_0, \dots, A_{N-1}$ modulo $998\,244\,353$, separated by spaces.

The second line should contain $B_0, \dots, B_{N-1}$ modulo $998\,244\,353$, separated by spaces.

Examples

Input 1

3
3 6 9

Output 1

18 39 162
162 66 18

Note

When a rational number is represented as an irreducible fraction $\frac{a}{b}$, its remainder modulo a prime $p$ is the unique integer $c$ such that $0 \le c < p$ and $a \equiv c \cdot b \pmod{p}$, provided that $b$ is not a multiple of $p$.

In this problem, it can be proven that for all possible inputs, $A_0, \dots, A_{N-1}$ and $B_0, \dots, B_{N-1}$ are rational numbers, and when each is represented as an irreducible fraction, the denominator is not a multiple of $998\,244\,353$.