分数: 2000 点
问题陈述
给你一个连通图 N 顶点和 M 边缘。顶点已编号 1 to N。的 i第一条边是长度为无向的边 C_i 连接顶点 A_i 和顶点 B_i.
另外,奇数 MOD 。
你将得到 Q 查询,应予以处理。查询采用以下形式:
- 中给出 i第一个查询是 S_i, T_i 和 R_i。打印
YES如果存在来自 Vertex 的路径 S_i 到顶点 T_i 其长度为 R_i 模数 MOD,并打印NO否则。一条路径可以多次遍历同一条边,或者使用刚刚使用过的边返回。
这里,在这个问题中,路径的长度是 不 其边本身的长度之和,但路径中使用的第一条边的长度乘以 1,第二条边乘以 2,第三条边乘以 4,等等。 (更正式地说,让 L_1,...,L_k 是所使用的边缘的长度,按此顺序。该路径的长度是 L_i \times 2^{i-1}.)
约束
- 1 \leq N,M,Q \leq 50000
- 3 \leq MOD \leq 10^{6}
- MOD 是奇数。
- 1 \leq A_i,B_i\leq N
- 0 \leq C_i \leq MOD-1
- 1 \leq S_i,T_i \leq N
- 0 \leq R_i \leq MOD-1
- 给定的图形已连接。 (它可能包含自环或多条边。)
输入
输入由标准输入按以下格式给出:
N M Q MOD A_1 B_1 C_1 \vdots A_M B_M C_M S_1 T_1 R_1 \vdots S_Q T_Q R_Q
输出
打印以下问题的答案 i- 第一个查询 i第行。
示例输入 1
3 2 2 2019 1 2 1 2 3 2 1 3 5 1 3 4
示例输出 1
YES NO
每个查询的答案如下:
- 第一个查询:如果我们采取路径 1,2,3,其长度为 1 \times 2^0 + 2 \times 2^1 = 5,因此存在一条长度为 5 模数 2019。答案是
YES. - 第二个查询:无论我们从 Vertex 采取什么路径 1 到顶点 3,它的长度永远不会 4 模数 2019。答案是
NO.
示例输入 2
6 6 3 2019 1 2 4 2 3 4 3 4 4 4 5 4 5 6 4 6 1 4 2 6 1110 3 1 1111 4 5 1112
示例输出 2
YES NO NO
示例输入 3
1 2 3 25 1 1 1 1 1 2 1 1 13 1 1 6 1 1 14
示例输出 3
YES YES YES
示例输入 4
10 15 10 15 1 2 1 2 3 6 3 4 6 2 5 1 5 6 1 4 7 6 1 8 11 2 9 6 5 10 11 9 10 11 3 6 1 2 5 1 2 7 11 9 10 11 5 6 11 1 3 5 9 8 3 7 7 7 7 10 13 4 1 10 9 3 12 10 10 14 9 2 1 6 6 5 8 8 4
示例输出 4
YES NO NO NO NO NO NO YES YES NO