Given an undirected graph with n vertices and m weighted edges. The weight of each edge can be expressed in the form 2a×3b. For q queries of the form u,v,a,b, check whether there exists a path from u to v such that the least common multiple (LCM) of the weights of the edges on the path equals 2a×3b. A path can include repeated edges.
### Input
- The first line contains two integers n and m.
- The next m lines each contain four integers u,v,a,b, representing an edge from u to v with weight 2a×3b.
- The next line contains an integer q.
- The next q lines each contain four integers u,v,a,b, a query.
### Output
- For each query, print Yes if there exists a valid path; otherwise, print No.
### Constraints
- 1≤n,q≤5×104.
- 1≤m≤105.
- 1≤u,v≤n.
- 1≤a,b≤2×109.
### Sample Test
Input:
4514211312342212132432542231433134423221322
Output
YesYesNoNoYes
