Graph LCM Path Query

You are given an undirected graph with n vertices and m edges. The vertices are numbered 1,2,…,n. Each edge has a positive weight and every weight can be represented in the form \(2^x \times 3^y\) for some non‐negative integers \(x\) and \(y\).

There are \(q\) queries. In each query, you are given four integers \(u, v, A, B\). Your task is to determine whether there exists a path from vertex \(u\) to vertex \(v\) (a path may visit vertices multiple times) such that if you take the weights of the edges on the path and compute their least common multiple (LCM), the result is
\[ 2^A \times 3^B. \]

Definitions:

• Least Common Multiple: Given \(k\) numbers \(a_1, a_2, \ldots, a_k\), their LCM is the smallest positive integer that is divisible by each \(a_i\). In our context, if the weights on the path are \(w_1, w_2, \ldots, w_k\) and each \(w_i = 2^{x_i} \times 3^{y_i}\), then \[ LCM(w_1, w_2, \ldots, w_k) = 2^{\max_i\{x_i\}} \times 3^{\max_i\{y_i\}}. \]
• Path: A sequence of vertices \(P_1, P_2, \ldots, P_k\) (with \(k \ge 2\)) such that for any \(1 \le i < k\), there is an edge between \(P_i\) and \(P_{i+1}\).

Note: The path is not required to be simple (vertices may repeat).

Task: For each query, determine if there is any path from \(u\) to \(v\) using only edges whose weights satisfy \(x \le A\) and \(y \le B\) (i.e. the allowed edges). Additionally, the path must include at least one edge with \(x=A\) and at least one edge with \(y=B\); only then the LCM of the weights will be exactly \(2^A \times 3^B\).

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of vertices and edges.

Then \(m\) lines follow. Each line contains three integers \(u\), \(v\) and \(w\), indicating there is an undirected edge between vertices \(u\) and \(v\) with weight \(w\). It is guaranteed that every weight \(w\) can be written in the form \(2^x \times 3^y\) for some non-negative integers \(x\) and \(y\).

The next line contains an integer \(q\) — the number of queries.

Each of the following \(q\) lines contains four integers \(u, v, A, B\) representing a query.

outputFormat

For each query, print a single line containing Yes if there exists a path meeting the above criteria, or No otherwise.

sample

4 4
1 2 2
2 3 3
3 4 6
4 1 1
4
1 3 1 1
1 4 1 0
2 4 1 1
1 1 0 0

Yes
No
Yes
Yes