OUPC2025 OPENコンテスト 2026/03/29 09:00 ~ 2026/03/29 14:00 5:00:00.000

E Pushback Sequence

問題
制限時間: 2 sec メモリ制限: 1024 MB
Pushback Sequence
Statement

人 \(1,2,\dots, N\) がいます。 人 \(i\) に数列を渡すと、渡した数列に対して「\(M\) 以下の正整数のうち \(A_i\) でないものを \(1\) つ選び、数列の末尾に追加する」という操作をちょうど \(B_i\) 回行ってできる数列と交換してくれます。

\(Q\) 個のクエリが与えられます。 \(q\) 番目のクエリでは正整数 \(L_q, R_q\) が与えられるので、以下の問いに答えてください。

  • 空の数列から始めて、数列を 人 \(L_q,L_q+1,\dots,R_q\) の順に渡して交換してもらうことで得られた数列を \(X\) とする。\(X\) としてあり得るものすべてに対する以下の値の総和を \(998244353\) で割ったあまりを求めてください。
    • \(X\) に含まれる要素の総和を \(M\) で割ったあまり

Input

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

\(N~M\)
\(A_1~A_2~\dots~A_N\)
\(B_1~B_2~\dots~B_N\)
\(Q\)
\(\mathrm{query}_{1}\)
\(\mathrm{query}_{2}\)
\(\vdots\)
\(\mathrm{query}_{Q}\)

\(q\) 番目のクエリ \(\mathrm{query}_q\) は以下の形式で与えられます。

\(L_q~R_q\)

入力は以下の制約をすべて満たします。

  • \(2 \leq N \leq 2 \times 10^5\)
  • \(3 \leq M \leq 10^8\)
  • \(1 \leq A_i \leq M\)
  • \(1 \leq B_i \leq 10^9\)
  • \(1 \leq Q \leq 2 \times 10^5\)
  • \(1 \leq L_q \leq R_q \leq N\)
  • 入力はすべて整数

Output

\(Q\) 行出力してください。

\(q\) 行目に \(\mathrm{query}_q\) に対する答えを出力してください。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

  • (10点):
    • \(N = 2\)
    • \(3 \leq M \leq 3000\)
    • \(1 \leq A_i \leq M\)
    • \(B_i = 1\)
    • \(Q=1\)
    • \(L_q=1\)
    • \(R_q=N\)
  • (20点):
    • \(2 \leq N \leq 3000\)
    • \(3 \leq M \leq 3000\)
    • \(1 \leq A_i \leq M\)
    • \(B_i = 1\)
    • \(Q=N\)
    • \(L_q=1\)
    • \(R_q=q\)
  • (70点): 追加制約なし

Examples

Input 1
2 3
1 2
1 1
1
1 2
Output 1
3
Input 2
4 100
31 41 59 26
1 1 1 1
4
1 1
1 2
1 3
1 4
Output 2
4919
485172
48029819
761972845

Note

Sample1: あり得る \(X\) は \((2, 1), (2, 3), (3, 1), (3, 3)\) の \(4\) 通りです。 \(X\) に含まれる要素の総和を \(M=3\) で割ったあまりはそれぞれ \(0,2,1,0\) となり、その総和は \(3\) です。

サンプル