问题描述

给定一个具有 $N$ 个顶点和 $M$ 条边的连通图。顶点从 $1$ 到 $N$ 编号。第 $i$ 条边是连接顶点 $A_i$ 和顶点 $B_i$ 的无向边，长度为 $C_i$。

此外，给定一个奇数 $MOD$。

你将得到 $Q$ 个查询，需要进行处理。查询的形式如下：

• 第 $i$ 个查询给出 $S_i$、$T_i$ 和 $R_i$。如果存在一条从顶点 $S_i$ 到顶点 $T_i$ 的路径，其长度对 $MOD$ 取模等于 $R_i$，则打印 YES，否则打印 NO。路径可以多次经过同一条边，或者使用刚刚使用的边返回。

在此问题中，路径的长度不是其边长的总和，而是路径中使用的第一条边的长度乘以 $1$，第二条边乘以 $2$，第三条边乘以 $4$，依此类推。（更正式地说，设 $L_1,\ldots,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$ 个查询的答案。

示例输入 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$，所以存在一条长度对 $2019$ 取模等于 $5$ 的路径。答案是 YES。
• 第二个查询：无论我们选择从顶点 $1$ 到顶点 $3$ 的哪条路径，其长度都不会对 $2019$ 取模等于 $4$。答案是 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