AT_agc031_f [AGC031F] Walk on Graph

给定一个有 $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 \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 翻译