Wrong Answer.wrong answer On line 85842 column 1, read Y, expected N.

#include <bits/stdc++.h>
#define int long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
#define lc ls, l, mid
#define rc rs, mid + 1, r

using namespace std;

const int maxn = 1e6 + 10;

struct edge {
	int u, v;
	edge() = default;
	edge(int u, int v): u(u), v(v) {}
};

struct node {
	vector<int> p;
};

struct op {
	int u, d;
	op() = default;
	op(int u, int d): u(u), d(d) {}
};

int n, m, k;
edge e[maxn];
node tr[maxn << 2];
int fa[maxn];
int h[maxn];

void insert(int u, int l, int r, int ql, int qr, int id) {
	if (ql <= l && r <= qr) {
		tr[u].p.push_back(id);
		return;
	}
	if (ql <= mid) insert(lc, ql, qr, id);
	if (qr > mid) insert(rc, ql, qr, id);
}

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

op st[maxn];
int top;

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (h[u] < h[v]) swap(u, v);
	fa[v] = u;
	st[++top] = op(v, h[u] == h[v]);
	if (h[u] == h[v]) h[u]++;
} 

int ans[maxn];

void solve(int u, int l, int r) {
	int lst = top;
	bool fl = 1;
	for (int i : tr[u].p) {
		int u = e[i].u, v = e[i].v;
		u = find(u), v = find(v);
		if (u == v) {
			for (int j = l; j <= r; j++) ans[j] = 0;
			fl = 0;
			break;
		} else {
			merge(u, find(e[i].v + n));
			merge(v, find(e[i].u + n));
		}
	}
	if (fl) {
		if (l == r) ans[l] = 1;
		else solve(lc), solve(rc);
	}
	while (top > lst) {
		h[fa[st[top].u]] -= st[top].d;
		fa[st[top].u] = st[top].u;
		top--;
	}
}

signed main() {
	cin >> n >> m >> k;
	for (int i = 1, x, y, l, r; i <= m; i++) {
		cin >> x >> y >> l >> r;
		e[i] = edge(x, y);
		if (l == r) continue;
		insert(1, 1, k, l + 1, r, i);
	}
	for (int i = 1; i <= n * 2; i++) fa[i] = i, h[i] = 1;
	solve(1, 1, k);
	for (int i = 1; i <= k; i++) {
		if (ans[i]) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}