← 返回题目列表

AtCoder · pakencamp_2023_day3_g

G. 取模

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

配点 : 100 点

問題文

T 测试用例解决以下问题。

长度 N 序列 有 A=(A_1,A_2,\ldots,A_N) 目前所有 关于 1\leq i\leq N 关于 A_i=0 。

你的目标都是 目标是确保 1\leq i\leq N 关于 A_i\equiv R_i\pmod{M} 成立。为此,您可以多次执行以下操作:(您也可以从不执行此操作。) 选择

  • 1\leq j\leq K 的整数 它等于 j 。 到第A 的 已知 P_j 个元素 添加 1 。此外,A 的 已知 Q_j 个元素 添加 1 。 将

确定目标是否可以实现。

制約

  • 1\leq T\leq 2\times 10^5
  • 1\leq N\leq 2\times 10^5
  • 2\leq M\leq 10^9
  • 1\leq K\leq 2\times 10^5
  • 0\leq R_i\lt M
  • 1\leq P_i\leq N
  • 1\leq Q_i\leq N
  • 1 包含在一个输入中 N 之和,K 的总和是 不超过 2\times 10^5 不超过

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

在这里, 表示第\mathrm{test}_i 为 i 个测试用例的信息,按以下格式给出:

N M K
R_1 R_2 \ldots R_N
P_1 Q_1
P_2 Q_2
\vdots
P_K Q_K

出力

请按顺序输出每个测试用例的答案,以换行符分隔。

对于每个测试用例,如果目标可以实现, Yes ,如果无法实现。 在第 No 。


入力例 1

3
6 3 5
0 1 0 1 2 0
1 2
1 6
4 5
5 2
5 6
6 4 7
2 3 1 2 3 0
1 4
3 2
3 5
6 5
4 6
1 2
2 4
4 5 4
2 4 2 4
1 3
1 3
2 4
2 4

出力例 1

Yes
No
Yes

1 个测试用例中,可以通过按以下顺序执行操作来实现目标:

  1. j=2 。 它变成A=(1,0,0,0,0,1) 。
  2. j=1 。 它变成A=(2,1,0,0,0,1) 。
  3. j=2 。 它变成A=(3,1,0,0,0,2) 。
  4. j=3 。 它变成A=(3,1,0,1,1,2) 。
  5. j=5 。 它变成A=(3,1,0,1,2,3) 。

最终全部 您可以确认已创建 1\leq i\leq 6 关于 A_i\equiv R_i\pmod{3} 。