Description

Given an undirected graph with $N$ vertices and $M$ edges (the vertices are numbered $1, 2, \ldots, N$). Each edge has a weight, and every weight can be factorized as $2^a \times 3^b$.

There are $q$ queries. In each query, you are given four parameters $u, v, a$, and $b$. Please determine whether there exists a path from vertex $u$ to vertex $v$ such that the least common multiple of the weights of the edges traversed along the path is exactly $2^a \times 3^b$.

Note: The path does not have to be simple.

Below are some definitions that may be useful. If they differ from other sources, use the definitions below for this problem:
Least common multiple: The least common multiple of $k$ numbers $a_1, a_2, \ldots, a_k$ is the smallest positive integer that is divisible by each $a_i$.

Path: A vertex sequence $P \colon P_1, P_2, \ldots, P_k$ is a path if and only if $k \geq 2$, and for any $1 \leq i < k$, there is an edge between $P_i$ and $P_{i+1}$.

Simple path: If in a path $P \colon P_1, P_2, \ldots, P_k$, it holds that $P_s \neq P_t$ for any $1 \leq s \neq t \leq k$, then $P$ is called a simple path.

Input Format

The first line contains two integers $N$ and $M$, the number of vertices and edges of the graph.

Each of the next $M$ lines contains four integers $u, v, a, b$, representing an edge between vertices $u$ and $v$ with weight $2^a \times 3^b$.

The next line contains an integer $q$, the number of queries.

Each of the next $q$ lines contains four integers $u, v, a$, and $b$, representing one query. See the problem description for details.

Output Format

For each query, output one line: Yes if such a path exists, otherwise output No (note: the first letter is uppercase, the rest are lowercase).

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

Yes 
Yes 
Yes 
No 
No

Hint

Constraints: $1 \leq N, q \leq 5 \times 10^4$, $1 \leq M \leq 10^5$, $0 \leq a, b \leq 10^9$.

Translated by ChatGPT 5