問題文

各言語でのメモリ使用量の確認と、ジャッジの MLE の挙動確認のための問題です。 サンプルケースを除き全部で 14 ケースありますが、最後のケースは AC できないことを想定しています。

p = 998244353 とおきます。 また、整数 N, K, x, y が与えられます。

数列 a_0, a_1, a_2, \ldots, a_{N-1} の一般項 a_n を次のように定義します。

• a_0 = x
• a_1 = y
• n \geq 2 のとき、 a_n = (a_{n-1} + a_{n-2} \cdot a_{\max (n-K, 0) }) \mod p

次に、長さ Q の数列 b_0, \ldots, b_{Q-1} が与えられます。 数列 c_0, \ldots, c_{Q-1} の一般項 c_n を次のように定義します。

• c_0 = a_{b_0}
• n \geq 1 のとき、 c_n = a_{(b_n + c_{n-1}) \mod N}

c_0, \ldots, c_{Q-1} を出力してください。

制約

• 1 \leq K \leq N \leq 7 \times 10^8
• (サンプルケースを除き) n ケース目では N=n \times (5 \times 10^7)
• 0 \leq x, y < 998244353
• 1 \leq Q \leq 10^6
• 0 \leq b_i < N
• 入力される値は全て整数

入力例 1

5 2 1 3
3
2
0
4

出力例 1

4
29
13