Migrated from Lutece 2937 安全通行

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 线段树分治 你来到一片神秘的大陆，这里有着 $n$ 个城镇，分别编号为 $1$，$2$ ... $n$，每两个城镇之间都有着一条可以双向通行的道路，然而因为战火、强盗、恶劣的天气，仅有少数的道路可以在一定时间内安全通行。

假设当前时刻为 $0$。现在，你一共知道 $m$ 个道路信息，第 $i$ 个信息的内容为 $u_i$ 城镇与 $v_i$ 城镇之间的道路在时间 $[l_i, r_i]$ 内可以安全通行。

接下来的 $k$ 个时刻，每个时刻 $i$ 你都会在脑中想到两个城镇 $a_i$，$b_i$，并结合已知的道路信息判断当前时刻能否安全地从城镇 $a_i$ 前往城镇 $b_i$（不考虑前往过程中消耗的时间）。由于你十分小心谨慎，对于 不知道信息 的道路你默认这条道路是危险的，即 不可通行。

Input

第一行输入三个整数 $n$, $m$ 和 $k$，表示城镇的数目 $n$，已知 $m$ 个道路信息，共有 $k$ 个时刻。

接下来的 $m$ 行每行输入四个数，第 $i$ 行输入的四个数 $u_i$，$v_i$ ，$l_i$ 和 $r_i$，表示城镇 $u_i$ 和城镇 $v_i$ 之间的道路在时间 $[l_i, r_i]$ 内可以安全通行。

最后 $k$ 行每行输入两个数字，第 $i$ 行输入的两个数 $a_i$ 和 $b_i$，分别表示判断当前时刻是否能通行的两个城镇。

Output

输出共 $k$ 行，对于每一个时刻，若两个城镇能安全互通，则输出 "$YES$"；否则，输出 "$NO$"（区分大小写、不加引号）。

Samples

3 3 3
1 2 1 1
2 3 1 2
1 3 2 3
1 3
2 3
1 2

YES
YES
NO

Constraints

$1 \leq n, m, k \leq 2 \times 10^5$，$1 \leq l_i \leq r_i \leq k$，$1 \leq u_i, v_i, a_i, b_i \leq n$

输入数据均为整数。

Resources

2023 UESTC ICPC Training for Data Structures