Problem Statement

Let $L=10^8$.

You are given an integer $N$ and a non-negative integer sequence $A=(A_1,A_2,\cdots,A_M)$ of length $M$ ($0 \leq A_i < L$). For each $k=1,2,\cdots,N$, solve the following problem:

There are $k$ red balls numbered from $1$ to $k$ and $k$ blue balls numbered from $1$ to $k$. Now, you will write a real number on each ball in the following way. Here, all random choices are independent.

• For each $1 \leq i \leq k$, the number written on red ball $i$ is $L \times (i-1)+A_{j_i}$. Here, $j_i$ is an integer chosen uniformly at random from the range between $1$ and $M$ (inclusive).
• For each $1 \leq i \leq k$, the number written on blue ball $i$ is a real number chosen uniformly at random from the range $[0,k \times L)$.

Find the probability, modulo $998244353$, that the following condition is satisfied after writing numbers on all balls.

• For any real number $x$ ($0 \leq x \leq k \times L$), "the number of red balls with a number written that is at most $x$" $\geq$ "the number of blue balls with a number written that is at most $x$".

Definition of probability modulo $998244353$ It can be proved that the desired probability is always a rational number. Also, under the constraints of this problem, it can be proved that if the desired rational number is represented as an irreducible fraction $\frac{P}{Q}$, then $Q \neq 0 \pmod{998244353}$. Therefore, there uniquely exists an integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353$. Output this $R$.

Constraints

• $1 \leq N \leq 250000$
• $1 \leq M \leq 250000$
• $0 \leq A_i < L=10^8$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \cdots A_M

Output

Output $N$ lines. The $i$-th line should contain the answer for $k=i$.