Description

Input

Output

Sample Input

Sample Output

HINT

考虑这道题的暴力算法，对于一个询问，将<=a,<=b的边都加进来，然后并查集check一下，总复杂度是O（mq*α）

可以想到类似于莫队的算法，先对边按a排序后分块，然后在计算某一块时，找出询问中符合本块a的询问。

对于前面的块的边的a，一定符合询问，所以把b排序后归并加入边，对于本块内的边暴力加，暴力删就行了（所以不能路径压缩）。

#include <cstdio>
#include <algorithm>
#include <cmath> 
#define maxn 100010
using namespace std;
void read(int &i)
{
	char x;
	for (x = getchar();x < '0';x = getchar());
	for (i = 0;x >= '0';x = getchar()) i = i * 10 + x - '0';
}
struct zhl
{
	int x,y,a,b,id;
	void init()
	{
		read(x);read(y);read(a);read(b);
	}
}e[maxn],q[maxn],tmp[maxn];
struct xfy
{
	int x,y,ma,mb,sz,f;
}re[maxn];
int cmp(zhl a,zhl b)
{
	return a.a == b.a?a.b<b.b:a.a<b.a;
}
int cmp1(zhl a,zhl b)
{
	return a.b == b.b?a.a<b.a:a.b<b.b;
}
int f[maxn],ma[maxn],mb[maxn],sz[maxn],tot,n,m,T,ans[maxn];

int find(int x)
{
	return f[x] == x?x:find(f[x]);
}
void check(int &x,int y)
{
	if (y > x) x = y;
}
void merge(int x,int y,int a,int b)
{
	int d1 = find(x),d2 = find(y);
	if (d1 == d2)
	{
		check(ma[d1],a);
		check(mb[d1],b);
		return;
	}
	if (sz[d1] > sz[d2]) swap(d1,d2);
	f[d1] = d2;sz[d2] += sz[d1];
	check(ma[d2],max(ma[d1],a));
	check(mb[d2],max(mb[d1],b));
}

void back(int x,int y)
{
	int d1 = find(x),d2 = find(y);
	if (sz[d1] > sz[d2]) swap(d1,d2);
	re[++tot].x = d1,re[tot].y = d2;
	re[tot].ma = ma[d2],re[tot].mb = mb[d2];
	re[tot].f = f[d1],re[tot].sz = sz[d2];
}

void recover()
{
	for (;tot;tot--)
	{
		int y = re[tot].y;
		f[re[tot].x] = re[tot].f;
		ma[y] = re[tot].ma;
		mb[y] = re[tot].mb;
		sz[y] = re[tot].sz;
	}
}

int main()
{
	read(n);read(m);
	for (int i = 1;i <= m;i++)
		e[i].init();
	read(T);
	for (int i = 1;i <= T;i++)
		q[i].init(),q[i].id = i;
	sort(e+1,e+m+1,cmp);
	sort(q+1,q+T+1,cmp1);
	int blk = (int)sqrt(m*log(m)/log(2));
	for (int i = 1;i <= m;i += blk)
	{
		int r1 = e[i].a,len = 0;
		for (int j = 1;j <= T;j++)
			if (q[j].a >= r1 && (i+blk > m||q[j].a < e[i+blk].a))
				tmp[++len] = q[j];
		for (int j = 1;j <= n;j++)
			f[j] = j,ma[j] = mb[j] = -1,sz[j] = 1;
		sort(e+1,e+i,cmp1);
		for (int j = 1,k = 1;j <= len;j++)
		{
			for (;k < i && tmp[j].b >= e[k].b;k++)
				merge(e[k].x,e[k].y,e[k].a,e[k].b);
			for (int w = i;w < i+blk&&w <= m;w++)
				if (e[w].a <= tmp[j].a && e[w].b <= tmp[j].b)
					back(e[w].x,e[w].y),merge(e[w].x,e[w].y,e[w].a,e[w].b);
			int d1 = find(tmp[j].x),d2 = find(tmp[j].y);
			if (d1 == d2 && ma[d1] == tmp[j].a && mb[d1] == tmp[j].b) ans[tmp[j].id] = 1;
			recover();
		}
	}
	for (int i = 1;i <= T;i++)
		ans[i]?puts("Yes"):puts("No");
	return 0;
}