记录编号	593670	评测结果	AAAAAAAAAA
题目名称	[HNOI 2016] 最小公倍数	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	18.366 s
提交时间	2024-09-07 15:24:45	内存使用	9.07 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e5+10,M = 500;

in ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m,q;
int c[N<<2];
struct node{ll u,v,a,b,id;}a[N<<2];
in bool cmp1(node x,node y){return x.a == y.a ? x.b < y.b : x.a < y.a;}
in bool cmp2(node x,node y){return x.b == y.b ? x.a < y.a : x.b < y.b;}
in int cmax(int &x,int y){x = max(x,y);}


node st[N];
int top;

struct DSU{
	int fa[N],siz[N],ma[N],mb[N];
	void build(){for(int i = 1;i <= n;i++)fa[i] = i,ma[i] = mb[i] = -1,siz[i] = 1;}
	int find(int x){return x == fa[x] ? x : find(fa[x]);}
	void merge(int x,int y,int a,int b,bool op){
		x = find(x),y = find(y);
		if(siz[x] < siz[y])swap(x,y);
		if(op)st[++top] = {x,y,ma[x],mb[x],siz[x]};
		if(x != y)fa[y] = x,siz[x] += siz[y];
		ma[x] = max({ma[x],ma[y],a}),mb[x] = max({mb[x],mb[y],b});
	}
	void del(){
		while(top){
			int x = st[top].u,y = st[top].v;
			ma[x] = st[top].a,mb[x] = st[top].b,siz[x] = st[top].id;
			fa[y] = y;
			top--;
		}
	}
}U;

vector<node>G[M];
int ans[N<<2];

struct block{
	int bl[N],L[M],R[M],B = 400,t,l;
	void build(){
		B = sqrt(m);
		t = (m-1)/B+1;
		for(int i = 1;i <= t;i++)L[i] = R[i-1] + 1,R[i] = min(m,B * i);
		for(int i = 1;i <= m;i++)bl[i] = (i-1)/B+1;
	}
	void add(int x,int r){
		while(a[l].b <= x && l <= r)U.merge(a[l].u,a[l].v,a[l].a,a[l].b,0),l++;
	}
	void work(){
		for(int i = 1;i <= t;i++){
			U.build();
			sort(a+1,a+R[i-1]+1,cmp2);
			l = 1;
			for(node now : G[i]){
				add(now.b,R[i-1]);
				for(int j = L[i];j <= R[i];j++)
					if(a[j].a <= now.a && a[j].b <= now.b)U.merge(a[j].u,a[j].v,a[j].a,a[j].b,1);
				int x = U.find(now.u),y = U.find(now.v);
				if(x == y && U.ma[x] == now.a && U.mb[x] == now.b)ans[now.id] = 1;
				U.del();
			}
		}
	}
}bl;


int main(){
	freopen("multiple.in","r",stdin);
	freopen("multiple.out","w",stdout);
	n = read(),m = read();
	for(int i = 1;i <= m;i++)a[i] = {read(),read(),read(),read(),0};
	sort(a+1,a+1+m,cmp1);
	for(int i = 1;i <= m;i++)c[i] = a[i].a;
	q = read();
	bl.build();
	for(int i = 1;i <= q;i++){
		int u = read(),v = read(),a = read(),b = read();
		int x = upper_bound(c+1,c+1+m,a) - c - 1;
		G[bl.bl[x]].pb({u,v,a,b,i});
	}
	for(int i = 1;i <= bl.t;i++)sort(G[i].begin(),G[i].end(),cmp2);
	bl.work(); 
	for(int i = 1;i <= q;i++)
		if(ans[i])printf("Yes\n");
		else printf("No\n");

	return 0;

}