High-Value Path Query

After reading the paper Distributed Exact Shortest Paths in Sublinear Time, you learned how to solve the distributed single-source shortest paths problem in \( \mathcal{O}(D^{1/3} \cdot (n \log n)^{2/3}) \). Now, Little Cyan Fish challenges you with a new task.

You are given a graph with n vertices (numbered from 1 to n) and m bidirectional edges. The i-th edge connects vertices u_i and v_i and has a weight w_i.

For any path between two vertices u and v, the value of the path is defined as the bitwise AND of the weights of all edges along that path. Little Cyan Fish loves a path if and only if its value is at least a given constant threshold V (i.e. the path satisfies \( \text{value} \ge V \)).

You will be given q queries. The i-th query consists of a pair of vertices \( (u_i, v_i) \). For each query, determine if there exists a path from \( u_i \) to \( v_i \) that Little Cyan Fish loves.

Hint: For a path to have a bitwise AND value at least \( V \), every edge in the path must have all bits that are set in \( V \) (i.e. for an edge weight \( w \), it must hold that \( w \,\&\, V = V \)). You can reduce this problem to checking connectivity in a subgraph where only edges satisfying this property are considered.

inputFormat

The first line contains four integers: n, m, V, and q — the number of vertices, the number of edges, the threshold for a loved path, and the number of queries, respectively.

Each of the next m lines contains three integers: ui, vi, and wi — indicating that there is an edge between vertices ui and vi with weight wi.

Each of the next q lines contains two integers: u and v representing a query asking whether there exists a loved path between vertices u and v.

outputFormat

For each query, output a single line with either YES if there exists a loved path between the given vertices, or NO otherwise.

sample

4 4 2 3
1 2 3
2 3 2
3 4 2
1 4 2
1 3
2 4
1 4

YES
YES
YES