题目描述

给定一个有 $N$ 个顶点、$M$ 条边的连通无向图。每个顶点编号为 $1,2,\ldots,N$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，边长为 $C_i$。此外，给定一个奇数 $MOD$。

有 $Q$ 个查询，每个查询的格式如下：

• 第 $i$ 个查询给出 $S_i,T_i,R_i$。请判断是否存在一条从顶点 $S_i$ 到顶点 $T_i$ 的路径，使得该路径的长度模 $MOD$ 后的余数为 $R_i$。这里允许多次经过同一条边，也允许刚走过的边立即返回。

但在本题中，路径的长度不是边长的简单和，而是第 $1$ 条经过的边的长度乘以 $1$，第 $2$ 条经过的边的长度乘以 $2$，第 $3$ 条经过的边的长度乘以 $4$，以此类推。更严格地说，若依次经过长度为 $L_1,\ldots,L_k$ 的边，则该路径的长度为 $\sum L_i \times 2^{i-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

输出

YES
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

输出

YES
NO
NO

样例 3

输入

1 2 3 25
1 1 1
1 1 2
1 1 13
1 1 6
1 1 14

输出

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

输出

YES
NO
NO
NO
NO
NO
NO
YES
YES
NO

说明/提示

数据范围

• $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$
• 给定的图是连通的（但可能有自环和重边）

样例解释 1

各个查询的答案如下：

• 第 $1$ 个查询：按 $1,2,3$ 的顺序前进，路径长度为 $1 \times 2^0 + 2 \times 2^1 = 5$，存在一条长度模 $2019$ 余 $5$ 的路径，所以答案为 YES。
• 第 $2$ 个查询：无论如何从顶点 $1$ 到顶点 $3$，路径长度模 $2019$ 都不可能为 $4$，所以答案为 NO。

由 ChatGPT 4.1 翻译