[HNOI2016]最小公倍数
题号:NC20118
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n),每条边上带有权值。所有权值都可以分解成2^a*3^b 的形式。
现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得 路径依次经过的边上的权值的最小公倍数为2^a*3^b。
注意:路径可以不是简单路径。
下面是一些可能有用的定义 :
最小公倍数:K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。
路径:路径P:P1,P2,…,Pk是顶点序列,满足对于任意1 ≤ i < k,节点Pi和Pi+1之间都有边相连。
简单路径:如果路径P:P1,P2,…,Pk中,对于任意1 ≤ s≠t ≤ k都有Ps≠Pt,那么称路径为简单路径。

输入描述:

输入文件的第一行包含两个整数N和M,分别代表图的顶点数和边数。
接下来M行,每行包含四个整数u、v、a、 b代表一条顶点u和v之间、权值为2^a*3^b的边。
接下来一行包含一个整数q,代表询问数。
接下来q行,每行包含四个整数u、v、a和b,代表一次询问。
询问内容请参见问题描述。1 ≤ n,q ≤ 50000、1 ≤ m ≤ 100000、0 ≤ a,b ≤ 10^9

输出描述:

对于每次询问,如果存在满足条件的路径,则输出一行Yes,否则输出一行 No(注意:第一个字母大写,其余字母小写) 。
示例1

输入

复制
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