← 返回题目列表

AtCoder · oupc2023_day1_o

O. 特殊矩阵

中文机器翻译题面 查看原题

配点 : 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. ( 1 点) N \leq 30
  2. ( 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的否定条件。