Background

This problem is an interactive problem, but here you should submit a full program.

Problem Description

In Ibaraki Prefecture, Japan, there are $N$ cities and $M$ roads. The cities are sorted in increasing order of population and are numbered from $0$ to $N - 1$. Each road connects two different cities and can be traveled in both directions. Using these roads, you can travel from any city to any other city.

You have planned $Q$ trips, numbered from $0$ to $Q - 1$. Trip $i(0 \leq i \leq Q - 1)$ goes from city $S_i$ to city $E_i$.

You are a werewolf. You have two forms: human form and wolf form. At the start of each trip, you are in human form. At the end of each trip, you must be in wolf form. During the trip, you must transform (from human form to wolf form) exactly once, and you can only transform inside a city (possibly at $S_i$ or $E_i$).

Life as a werewolf is not easy. When you are in human form, you must avoid cities with small populations, and when you are in wolf form, you must avoid cities with large populations. For each trip $i(0 \leq i \leq Q - 1)$, there are two thresholds $L_i$ and $R_i(0 \leq L_i \leq R_i \leq N - 1)$ that describe which cities must be avoided. More precisely, when you are in human form, you must avoid cities $0, 1, \ldots , L_i - 1$; when you are in wolf form, you must avoid cities $R_i + 1, R_i + 2, \ldots , N - 1$. This means that in trip $i$, you must transform in one of the cities $L_i, L_i + 1, \ldots , R_i$.

Your task is: for each trip, determine whether it is possible to travel from city $S_i$ to city $E_i$ while satisfying the restrictions above. Your route may have any length.

Input Format

The first line contains three positive integers $N, M, Q$, as described above.

The next $M$ lines each contain two non-negative integers. In these $M$ lines, the $j$-th line contains $X_{j - 1}, Y_{j - 1}$, meaning that road number $j - 1$ connects those two cities.

The next $Q$ lines each contain four non-negative integers. In these $Q$ lines, the $i$-th line contains $S_{i - 1}, E_{i - 1}, L_{i - 1}, R_{i - 1}$, meaning that trip number $i - 1$ starts at city $S_{i - 1}$, ends at city $E_{i - 1}$, and has the two thresholds.

Output Format

Output $Q$ lines, each containing an integer that is either $0$ or $1$. The integer on line $i$ indicates whether, for trip number $i - 1$, it is possible to travel from city $S_{i - 1}$ to city $E_{i - 1}$. Output $1$ if it is possible, otherwise output $0$.

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

1
0
0

10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

1
1
1
0
1
1
0
1
0
1

Hint

Constraints

• $2 \leq N \leq 200, 000$
• $N - 1 \leq M \leq 400, 000$
• $1 \leq Q \leq 200, 000$
• For each $0 \leq j \leq M - 1$
  • $0 \leq X_j \leq N - 1$
  • $0 \leq Y_j \leq N - 1$
  • $X_j \neq Y_j$
• You can travel from any city to any other city using the roads.
• Each pair of cities is directly connected by at most one road. In other words, for all $0 \leq j < k \leq M - 1$, $(X_j, Y_j) \neq (X_k, Y_k)$ and $(Y_j, X_j) \neq (X_k, Y_k)$.
• For each $0 \leq i \leq Q - 1$
  • $0 \leq L_i \leq S_i \leq N - 1$
  • $0 \leq E_i \leq R_i \leq N - 1$
  • $S_i \neq E_i$
  • $L_i \leq R_i$

Subtasks

• 1. (7 points) $N \leq 100$, $M \leq 200$, $Q \leq 100$.
• 2. (8 points) $N \leq 3, 000$, $M \leq 6, 000$, $Q \leq 3, 000$.
• 3. (34 points) $M = N - 1$ and each city is connected to at most two roads (all cities form a single line).
• 4. (51 points) No additional constraints.

Translated by ChatGPT 5