[HNOI2016]最小公倍数

题目描述

给定一张N个顶点M条边的无向图(顶点编号为1,2,...,n),每条边上带有权值。所有权值都可以分解成$2^a*3^b$的形式。 现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得路径依次经过的边上的权值的最小公倍数为$2^a*3^b$。 注意:路径可以不是简单路径。 下面是一些可能有用的定义,如果与其它地方定义不同,在本题中以下面的定义为准: 最小公倍数: $ k $ 个数 $ a_1 , a_2, \ldots, a_k $ 的最小公倍数是能被每个 $a_i$ 整除的最小正整数。 路径:顶点序列 $ P \colon P_1,P_2,\ldots,P_k $ 是一条路径,当且仅当 $k \geq 2$,且对于任意 $ 1 \leq i < k $ ,节点 $ P_i $ 和 $ P_{i+1} $ 之间都有边相连。 简单路径:如果路径 $ P \colon P_1,P_2,\ldots,P_k $ 中,对于任意 $ 1 \leq s \neq t \leq k $ 都有 $ P_s \neq P_t $ ,那么称 $P$ 为简单路径。

输入输出格式

输入格式


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

输出格式


对于每次询问,如果存在满足条件的路径,则输出一行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

输出样例 #1

Yes 
Yes 
Yes 
No 
No

说明

【数据范围】 1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9