外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

U - Nyan Nyan Nyan Nyan Infinite Maigai

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529

配点 550 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

一次元の各整数座標に、ちょうど11匹のねこがいます。

T=0T=0の時には、MM匹のねこだけが鳴いています。

その、鳴いているねこ ii の座標はAiA_iです。

m≥0m \ge 0において、ねこは、T=mT=mの時に、ちょうど DD 離れた位置の別のねこが1匹以上鳴いているとき、またそのときに限り、T=m+1T=m+1の時に鳴きます。

今からQQ個のクエリが与えられます。

クエリiiでは、T=BiT=B_iの時に鳴いているねこが何匹いるかmod  998244353\mod{998244353}で求めてください。

制約

  • 1≤M≤1051 \leq M \leq 10^5
  • 1≤D≤1051 \leq D \leq 10^5
  • ∣Ai∣≤108|A_i| \leq 10^{8}
  • AiA_iは重複しないにゃ
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 0≤Bi≤10100 \leq B_i \leq 10^{10}
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

MM DD A1A_1 …\ldots AMA_M QQ B1B_1 …\ldots BQB_Q

出力

QQ 行出力してください。 qq 行目には qq 番目のクエリの答えを出力してください。

サンプル 1

入力

5 5
1 2 3 4 5
5
0 1 2 3 222222222

出力

5
10
15
20
112866762

サンプル 2

入力

5 3
1 2 3 4 5
5
0 1 2 3 222222222

出力

5
10
15
20
112866762

サンプル 3

入力

5 2
1 2 3 4 5
5
0 1 2 3 222222222

出力

5
9
13
17
888888893

サンプル 4

入力

5 1
1 2 3 4 5
5
0 1 2 3 222222222

出力

5
7
9
11
444444449

参加受付は終了しました。