AT_oupc2023_day1_o Special Matrix

この問題では以下の数式表現を用います。 - $ 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` を出力してください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ P $ $ a $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ $ \vdots $ $ A_K $ $ B_K $ $ C_K $ $ D_K $ $ Q $ $ E_1 $ $ F_1 $ $ E_2 $ $ F_2 $ $ \vdots $ $ E_Q $ $ F_Q $

$ Q $ 行出力してください。 $ q $ 行目には、 $ q $ 番目のクエリに対する答えを出力してください。

### 小課題 1. ( $ 1 $ 点) $ N \leq 30 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1 $ つめのクエリの場合、例えば $ M=\begin{pmatrix} 2 & 0 \\ 3 & 2 \end{pmatrix} $ は $ M_{2,2} $ が最小であるスペシャル行列です。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 2 スペシャル行列は存在しません。 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 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 $ - 入力はすべて整数