#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 6e6 + 200;
ve<int> gr1[N]; int p1[N], w1 = 0;
inline int par1(int v) { if (p1[v] == v) { return v; } return (p1[v] = par1(p1[v])); }
inline void add1(int a, int b) {
a = par1(a), b = par1(b);
if (a == b) return;
int c = w1++;
p1[a] = p1[b] = p1[c] = c;
gr1[c].pb(a);
if (a ^ b) gr1[c].pb(b);
} int ti1 = 0;
int in1[N], out1[N];
inline void dfs1(int v) {
in1[v] = ti1++;
for (auto &to : gr1[v]) dfs1(to);
out1[v] = ti1 - 1;
}
ve<int> gr2[N]; int p2[N], w2 = 0;
inline int par2(int v) { if (p2[v] == v) { return v; } return (p2[v] = par2(p2[v])); }
inline void add2(int a, int b) {
a = par2(a), b = par2(b);
if (a == b) return;
int c = w2++;
p2[a] = p2[b] = p2[c] = c;
gr2[c].pb(a);
if (a ^ b) gr2[c].pb(b);
} int ti2 = 0;
int in2[N], out2[N];
inline void dfs2(int v) {
in2[v] = ti2++;
for (auto &to : gr2[v]) dfs2(to);
out2[v] = ti2 - 1;
}
int fe[N];
inline void upd(int i, int x) { i += 3; for (; i < N; i += i & -i) fe[i] += x; }
inline int get(int i) { int ans = 0; i += 3; for (; i; i -= i & -i) { ans += fe[i]; } return ans; }
inline int get(int l, int r) { return get(r) - get(l - 1); }
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int n = N;
int m = sz(X); int q = sz(S);
ve<array<int,3>> e(m);
for (int i = 0; i < m; ++i) {
int v, u;
tie(v, u) = mpp(X[i], Y[i]);
e[i] = {min(v, u), v, u};
} sort(all(e));
w1 = w2 = n;
for (int i = 0; i < n; ++i) p1[i] = p2[i] = i;
ve<array<int,5>> que(q);
for (int i = 0; i < q; ++i) que[i] = {S[i], E[i], L[i], R[i], i};
sort(all(que), [](const auto &a, const auto &b) { return a[2] > b[2]; });
ve<int> rt1(q), rt2(q);
int ptr = sz(e) - 1, ptr1 = 0;
for (auto &[v, u, l, r, id] : que) {
while (~ptr && e[ptr][0] >= l) {
add1(e[ptr][1], e[ptr][2]);
--ptr;
} rt1[id] = par1(v);
}
for (int i = 0; i < m; ++i) {
int v, u;
tie(v, u) = mpp(X[i], Y[i]);
e[i] = {max(v, u), v, u};
} sort(all(e));
sort(all(que), [](const auto &a, const auto &b) { return a[3] < b[3]; });
for (auto &[v, u, l, r, id] : que) {
while (ptr1 < sz(e) && e[ptr1][0] <= r) {
add2(e[ptr1][1], e[ptr1][2]);
++ptr1;
} rt2[id] = par2(u);
}
for (int i = 0; i < w1; ++i) if (p1[i] == i) dfs1(i);
for (int i = 0; i < w2; ++i) if (p2[i] == i) dfs2(i);
ve<int> a(n), b(n);
for (int i = 0; i < n; ++i) a[i] = in1[i], b[i] = in2[i];
sort(all(a)), sort(all(b));
a.erase(unique(all(a)), a.end());
b.erase(unique(all(b)), b.end());
ve<int> c(n), d(n);
for (int i = 0; i < n; ++i) c[i] = lower_bound(all(a), in1[i]) - a.begin();
for (int i = 0; i < n; ++i) d[i] = lower_bound(all(b), in2[i]) - b.begin();
ve<array<int,5>> hui;
for (int i = 0; i < q; ++i) {
int l1 = in1[rt1[i]], r1 = out1[rt1[i]];
int l2 = in2[rt2[i]], r2 = out2[rt2[i]];
l1 = lower_bound(all(a), l1) - a.begin();
r1 = upper_bound(all(a), r1) - a.begin() - 1;
l2 = lower_bound(all(b), l2) - b.begin();
r2 = upper_bound(all(b), r2) - b.begin() - 1;
if (l1 > r1 || l2 > r2) continue;
hui.pb({r2 , l1, r1, +1, i});
hui.pb({l2 - 1, l1, r1, -1, i});
}
sort(all(hui));
ve<pii> al(n);
for (int i = 0; i < n; ++i) al[i] = {d[i], i};
sort(all(al));
ptr = 0;
ve<int> ans(q);
for (auto &[pos, l, r, sgn, id] : hui) {
while (ptr < sz(al) && al[ptr].fi <= pos) {
upd(c[al[ptr].se], +1);
++ptr;
} ans[id] += get(l, r) * sgn;
}
for (auto &i : ans) i = !!i;
return ans;
}
#ifdef LOCAL
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int N = read_int();
int M = read_int();
int Q = read_int();
std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
for (int j = 0; j < M; ++j) {
X[j] = read_int();
Y[j] = read_int();
}
for (int i = 0; i < Q; ++i) {
S[i] = read_int();
E[i] = read_int();
L[i] = read_int();
R[i] = read_int();
}
std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
for (size_t i = 0; i < A.size(); ++i) {
printf("%d\n", A[i]);
}
return 0;
}
#endif
