{"problem":{"name":"Walk on Graph","description":{"content":"You are given a connected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$. The $i$\\-th edge is an undirected edge of length $C_i$ connecting Vertex $A_i$ and Vertex $B_i$. ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc031_f"},"statements":[{"statement_type":"Markdown","content":"You are given a connected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$. The $i$\\-th edge is an undirected edge of length $C_i$ connecting Vertex $A_i$ and Vertex $B_i$.\nAdditionally, an odd number $MOD$ is given.\nYou will be given $Q$ queries, which should be processed. The queries take the following form:\n\n*   Given in the $i$\\-th query are $S_i$, $T_i$ and $R_i$. Print `YES` if there exists a path from Vertex $S_i$ to Vertex $T_i$ whose length is $R_i$ modulo $MOD$, and print `NO` otherwise. A path may traverse the same edge multiple times, or go back using the edge it just used.\n\nHere, in this problem, the length of a path is **NOT** the sum of the lengths of its edges themselves, but the length of the first edge used in the path gets multiplied by $1$, the second edge gets multiplied by $2$, the third edge gets multiplied by $4$, and so on. (More formally, let $L_1,...,L_k$ be the lengths of the edges used, in this order. The length of that path is the sum of $L_i \\times 2^{i-1}$.)\n\n## Constraints\n\n*   $1 \\leq N,M,Q \\leq 50000$\n*   $3 \\leq MOD \\leq 10^{6}$\n*   $MOD$ is odd.\n*   $1 \\leq A_i,B_i\\leq N$\n*   $0 \\leq C_i \\leq MOD-1$\n*   $1 \\leq S_i,T_i \\leq N$\n*   $0 \\leq R_i \\leq MOD-1$\n*   The given graph is connected. (It may contain self-loops or multiple edges.)\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$ $MOD$\n$A_1$ $B_1$ $C_1$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n$S_1$ $T_1$ $R_1$\n$\\vdots$\n$S_Q$ $T_Q$ $R_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc031_f","tags":[],"sample_group":[["3 2 2 2019\n1 2 1\n2 3 2\n1 3 5\n1 3 4","YES\nNO\n\nThe answer to each query is as follows:\n\n*   The first query: If we take the path $1,2,3$, its length is $1 \\times 2^0 + 2 \\times 2^1 = 5$, so there exists a path whose length is $5$ modulo $2019$. The answer is `YES`.\n*   The second query: No matter what path we take from Vertex $1$ to Vertex $3$, its length will never be $4$ modulo $2019$. The answer is `NO`."],["6 6 3 2019\n1 2 4\n2 3 4\n3 4 4\n4 5 4\n5 6 4\n6 1 4\n2 6 1110\n3 1 1111\n4 5 1112","YES\nNO\nNO"],["1 2 3 25\n1 1 1\n1 1 2\n1 1 13\n1 1 6\n1 1 14","YES\nYES\nYES"],["10 15 10 15\n1 2 1\n2 3 6\n3 4 6\n2 5 1\n5 6 1\n4 7 6\n1 8 11\n2 9 6\n5 10 11\n9 10 11\n3 6 1\n2 5 1\n2 7 11\n9 10 11\n5 6 11\n1 3 5\n9 8 3\n7 7 7\n7 10 13\n4 1 10\n9 3 12\n10 10 14\n9 2 1\n6 6 5\n8 8 4","YES\nNO\nNO\nNO\nNO\nNO\nNO\nYES\nYES\nNO"]],"created_at":"2026-03-03 11:01:14"}}