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 分）无其他额外限制 ## 样例说明 1 对于第 1 个查询，例如 $M=\begin{pmatrix} 2 & 0 \\ 3 & 2 \end{pmatrix}$ 就是 $M_{2,2}$ 最小的“特殊矩阵”。 该测试用例满足子任务 1 的约束。 ## 样例说明 2 不存在满足条件的“特殊矩阵”。 该测试用例满足子任务 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$ - 所有输入均为整数。 由 ChatGPT 5 翻译