AT_agc076_d [AGC076D] Stochastic Dominance

$ L=10^8 $ とします． 整数 $ N $ 及び長さ $ M $ の非負整数列 $ A=(A_1,A_2,\cdots,A_M) $ ( $ 0 \leq A_i < L $ ) が与えられます． 各 $ k=1,2,\cdots,N $ に対して，次の問題を解いてください． $ 1 $ から $ k $ までの番号のついた $ k $ 個の赤いボールと， $ 1 $ から $ k $ までの番号のついた $ k $ 個の青いボールがあります． 今から以下の方法で各ボールに実数を書き込みます． なお，すべてのランダムな選択は独立です． - 各 $ 1 \leq i \leq k $ について，赤いボール $ i $ に書き込む数は， $ L \times (i-1)+A_{j_i} $ である． ただし $ j_i $ は $ 1 $ 以上 $ M $ 以下の範囲で一様ランダムに選ばれた整数である． - 各 $ 1 \leq i \leq k $ について，青いボール $ i $ に書き込む数は $ [0,k \times L) $ の範囲で一様ランダムに選ばれた**実数**である． すべてのボールに数を書き込んだあと以下の条件が満たされている確率を $ \text{mod }{998244353} $ で求めてください． - 任意の実数 $ x $ ( $ 0 \leq x \leq k \times L $ ) に対して，「 $ x $ 以下の数が書き込まれた赤いボールの個数」 $ \geq $ 「 $ x $ 以下の数が書き込まれた青いボールの個数」が成立する． 確率 $ \text{mod }{998244353} $ の定義 求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 $ \frac{P}{Q} $ で表した時、 $ Q \neq 0 \pmod{998244353} $ となることが証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_M $

$ N $ 行出力せよ． $ i $ 行目には $ k=i $ に対する答えを出力せよ．

### Sample Explanation 1 - $ k=1 $ : 条件を満たす確率は $ 1/2 $ です． - $ k=2 $ : 条件を満たす確率は $ 5/16 $ です． ### Constraints - $ 1 \leq N \leq 250000 $ - $ 1 \leq M \leq 250000 $ - $ 0 \leq A_i < L=10^8 $ - 入力はすべて整数