Problem Statement

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$.

Additionally, an odd number $MOD$ is given.

You will be given $Q$ queries, which should be processed. The queries take the following form:

• 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.

Here, 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}$.)

Constraints

• $1 \leq N,M,Q \leq 50000$
• $3 \leq MOD \leq 10^{6}$
• $MOD$ is odd.
• $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$
• The given graph is connected. (It may contain self-loops or multiple edges.)

Input

Input is given from Standard Input in the following format:

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

Output

Print the answers to the $i$-th query in the $i$-th line.