注意

この問題は Have Another Go (Hard) の制約緩和版です。Hard版との違いは、$6\leq N\leq 5 \times 10^{5}$ 、$M=2$ であることです。

ストーリー

必ずしもこの項を読む必要はない。

tfl君は $N$ 個のマスを $1$ 周して落ちているコインを集めるすごろくで遊んでいます。しかし...

tfl君「$1$ 周したけど全然コインが取れなかった...」

highlighterはかせ「それじゃあ、$2$ 周してもいいことにしよう。これで億万長者間違いなしじゃ！」

tfl君「$2$ 周じゃあんま変わらないと思うんだけど...」

highlighterはかせ「もっと多くすると通り数を求めるのが大変じゃろう」

tfl君「え、いや通り数を求めるつもりはないんだけど!?」

問題文

tfl君は次のようなゲームで遊んでいます。

• 変数 $X$ と空の配列 $Y$ を用意する。はじめ $X$ の値は $0$ に等しい。
• 以下の一連の操作を行う。
  • $X$ を $Y$ の末尾に付け加える。
  • $1$ 以上 $6$ 以下の整数が等確率で出るサイコロを振る。
  • $X$ にサイコロで出た目の数を加える。
  • $X \geq NM$ なら操作を終える。そうでないなら、またこの操作を繰り返す。

ただし、この問題では $M=2$ です。

$i=1,2,\ldots k$ について、以下の問いに答えてください。

ただし、サイコロを振る操作は毎回独立です。

制約

• $6 \leq N \leq 5 \times 10^{5}$
• $M=2$
• $1 \leq k \leq 5000$
• $1 \leq C_{i} \lt N$
• 入力はすべて整数

入力

$N~~~M~~~k$
$C_{1} ~~~ C_{2} ~ \ldots ~ C_{k}$

出力

$k$ 行出力せよ。 $i$ 行目には、 $C_{i}$ に対する答えを $998244353$ で割った余りを出力せよ。

サンプル

7 2 4
1 2 3 4

29503
29564
29684
29920