問題文

この問題では以下の数式表現を用います。

• M_{i,j} : 行列 M の i 行 j 列成分
• \text{GCD}(x,y) : x と y の最大公約数

非負整数を成分とする N 行 N 列の行列 M が以下の条件を満たすとき、"スペシャル行列"と呼ぶことにします。

• 1 \leq i,j \leq N に対し、i < j のとき M_{i,j}=0 、i \geq j のとき M_{i,j}>0
• M_{1,1}=a
• 長さ N の等比数列 X= ( X_1,X_2, \dots ,X_N ) が存在して、 1 \leq j \leq i \leq N に対し、(M^P) _ {i,j}=M_{i,j} \times X_{i-j+1}
• 1 \leq k \leq Kに対し、\text{GCD}(M_{A_k,B_k},C_k)=D_k

クエリが Q 個与えられます。 q 番目のクエリではスペシャル行列 M について M_{E_q,F_q} の最小値を 998244353 で割った余りを出力してください。 ただし、最小値が存在しない場合は -1 を出力してください。

制約

• 1 \leq N \leq 1{,}000
• 2 \leq P \leq 10^{9}
• 1 \leq a \leq 10^{9}
• 0 \leq K \leq \min(1{,}000,\frac{N(N-1)}{2})
• 1 \leq B_k < A_k \leq N
• (A_1,B_1),(A_2,B_2), \dots ,(A_K,B_K) はすべて異なる
• 1 \leq D_k \leq C_k \leq 10^{9}
• C_k は D_k で割り切れる
• 1 \leq Q \leq 70
• 1 \leq F_q \leq E_q \leq N
• 入力はすべて整数

小課題

1. ( 1 点) N \leq 30
2. ( 99 点) 追加の制約はない

入力例 1

2 3 2 1
2 1 2 1
2
2 2
2 1

出力例 1

2
1

1 つめのクエリの場合、例えばM=\begin{pmatrix} 2 & 0 \\ 3 & 2 \end{pmatrix} は M_{2,2} が最小であるスペシャル行列です。

このテストケースは小課題 1 の制約を満たします。

入力例 2

3 3 3 2
2 1 3 1
3 2 3 1
1
3 2

出力例 2

-1

スペシャル行列は存在しません。

このテストケースは小課題 1 の制約を満たします。