#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "werewolf.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() { cout << "\n"; }
template<typename T, typename...U>
void dout(T t, U...u) { cout << t << (sizeof...(u) ? ", " : ""), dout(u...); }
#else
#define debug(...) 7122s
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 2e5 + 5;
const int H = __lg(SIZE);
int n, m, q;
vector<int> ans, adj[SIZE], ask[SIZE];
struct DSU {
int to[SIZE];
DSU() = default;
void init() {
iota(to, to + n, 0);
}
int dsu(int x) {
return x == to[x] ? x : (to[x] = dsu(to[x]));
}
};
struct Tree {
vector<int> adj[SIZE];
int root, to[SIZE][H + 1], h[SIZE];
int dfsid, in[SIZE], out[SIZE], w[SIZE];
DSU dsu;
Tree() = default;
void init() {
dfsid = -1;
dsu.init();
}
void add(int a, int b) {
a = dsu.dsu(a), b = dsu.dsu(b);
if (a == b) return;
adj[a].pb(b);
dsu.to[b] = a;
root = a;
}
void build() {
auto dfs = [&](auto dfs, int pos)->void {
in[pos] = ++dfsid;
w[pos] = 1;
for (int np : adj[pos]) {
h[np] = h[pos] + 1;
to[np][0] = pos;
dfs(dfs, np);
w[pos] += w[np];
}
out[pos] = dfsid;
};
to[root][0] = root;
dfs(dfs, root);
FOR (j, 1, H) FOR (i, 0, n - 1) to[i][j] = to[to[i][j - 1]][j - 1];
}
int sch(int pos, int lim, int ty) {
for (int i = H; i >= 0; i--) if ((ty == 1 && to[pos][i] >= lim) || (ty == 2 && to[pos][i] <= lim)) pos = to[pos][i];
return pos;
}
} t1, t2;
int bit[SIZE];
void upd(int pos, int x) {
for (pos++; pos <= n; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
int re = 0;
for (pos++; pos; pos -= pos & -pos) re += bit[pos];
return re;
}
int que(int l, int r) {
return que(r) - que(l - 1);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N, m = X.size(), q = S.size();
ans.resize(q);
FOR (i, 0, m - 1) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
t1.init(), t2.init();
for (int i = n - 1; i >= 0; i--) for (int j : adj[i]) if (i < j) t1.add(i, j);
FOR (i, 0, n - 1) for (int j : adj[i]) if (i > j) t2.add(i, j);
t1.build(), t2.build();
FOR (i, 0, q - 1) {
S[i] = t1.sch(S[i], L[i], 1);
E[i] = t2.sch(E[i], R[i], 2);
ask[S[i]].pb(i);
}
auto add = [&](auto add, int pos, int coef)->void {
upd(t2.in[pos], coef);
for (int np : t1.adj[pos]) add(add, np, coef);
};
auto dfs = [&](auto dfs, int pos)->void {
int son = -1;
for (int np : t1.adj[pos]) if (son == -1 || t1.w[np] > t1.w[son]) son = np;
for (int np : t1.adj[pos]) if (np != son) {
dfs(dfs, np);
add(add, np, -1);
}
if (son != -1) dfs(dfs, son);
for (int np : t1.adj[pos]) if (np != son) add(add, np, 1);
upd(t2.in[pos], 1);
for (int i : ask[pos]) {
int l = t2.in[E[i]], r = t2.out[E[i]];
ans[i] = que(l, r) > 0;
}
};
dfs(dfs, 0);
return ans;
}
/*
in1
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
out1
1
0
0
*/
#ifdef WAIMAI
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();
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();
}
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
