ミーシャは自分が美しいと思ういくつかの整数をノートに書き留め、プラスとマイナスで遊びに行きました。彼は、プラスとマイナスからなる文字列について、両方の記号の個数が等しく、かつ末尾に美しい個数のマイナスが連続しているとき、その文字列はバランスが取れていると考えます。長さ $2, 4, \dots, 2n$ のバランスが取れた文字列はそれぞれいくつありますか？答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを求めてください。

入力

1 行目には、文字列の最大長に関するパラメータとミーシャのノートにある整数の個数を表す 2 つの整数 $n$ と $m$ ($1 \le n, m \le 200000$) が与えられます。

次の行には、範囲 $[0, n]$ 内の相異なる $m$ 個の非負整数（ミーシャのノートに書かれた数）が与えられます。

出力

答えを $998244353$ で割った余りを $n$ 行にわたって出力してください。

入出力例

入力

5 3
1 2 3

出力

1
3
10
34
120