配点 : 100 点
問題文
在这个问题中使用以下数学表达式。
- 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 点) N \leq 30
- ( 99 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
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
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的否定条件。