题目描述

译自 NOISG 2023 Final T4. Curtains

兔子本森正在他的飞机上组织一场表演！

他有一个舞台，分为 $n$ 个部分，编号从 $1$ 到 $n$，从左到右排列。他还有 $m$ 块幕布，编号从 $1$ 到 $m$。

这 $m$ 块幕布每块都可以放下。放下幕布 $i$ 会覆盖部分 $l[i]$ 到 $r[i]$。幕布配置是一组放下的幕布。对于给定的幕布配置，部分 $x$ $(1 \leq x \leq n)$ 被覆盖，当且仅当存在一块放下的幕布 $i$，满足 $l[i] \leq x \leq r[i]$。

本森希望举办总计 $q$ 场表演，编号从 $1$ 到 $q$。对于每场表演 $j$，本森需要一个幕布配置，使得部分 $s[j]$ 到 $e[j]$ 被覆盖，且其他部分不被覆盖。更正式地，对于每个 $1 \leq x \leq n$：

• 若 $s[j] \leq x \leq e[j]$，部分 $x$ 被覆盖。
• 否则，部分 $x$ 不被覆盖。

对于这 $q$ 场表演中的每一场，帮助本森确定是否存在满足他要求的幕布配置。

输入格式

程序需从标准输入读取数据。

输入的第一行包含三个空格分隔的整数 $n, m, q$，分别表示舞台部分数量、幕布数量和表演数量。

接下来的 $m$ 行，每行包含两个空格分隔的整数，第 $i$ 行包含 $l[i]$ 和 $r[i]$，描述幕布 $i$ 可覆盖的部分范围。

接下来的 $q$ 行，每行包含两个空格分隔的整数，第 $j$ 行包含 $s[j]$ 和 $e[j]$，描述表演 $j$ 需要覆盖的部分范围。

输出格式

程序需向标准输出输出结果。

输出 $q$ 行。在第 $j$ 行，若可以使用幕布覆盖第 $j$ 场表演所需的部分输出 YES，否则输出 NO。

6 2 3
1 2
3 4
1 3
1 4
1 5

NO
YES
NO

本森有 $6$ 个舞台部分和 $2$ 块幕布。幕布 $1$ 覆盖部分 $1$ 和 $2$，幕布 $2$ 覆盖部分 $3$ 和 $4$。

无法精确覆盖部分 $1$ 到 $3$。也无法精确覆盖部分 $1$ 到 $5$。可以使用两块幕布精确覆盖部分 $1$ 到 $4$。

这个样例满足所有子任务的限制。

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

NO
NO
YES
NO
YES
NO
NO
NO
NO
YES

这个样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n, m, q \leq 500000$
• $1 \leq l[i] \leq r[i] \leq n$（对于所有 $1 \leq i \leq m$）
• $1 \leq s[j] \leq e[j] \leq n$（对于所有 $1 \leq j \leq q$）

详细子任务附加限制及分值如下表所示：