markdown

F. Katya 与线段集合

时间限制：每个测试点 $3.5$ 秒
内存限制：每个测试点 $512$ 兆字节
输入：标准输入
输出：标准输出

题目描述

今天是 Katya 非常重要的一天。她有一场编程课的考试。和往常一样，她拿到了一道有趣的题目，并且很快就解出来了。你能解决这道题吗？

你有 $n$ 个有序的线段集合。每条线段可以用一对整数 $[l, r]$ 表示，其中 $l \le r$。每个集合可以包含任意数量的线段（甚至可以为 $0$ 条）。不同的线段可能完全相同。

此外，你还会收到 $m$ 个查询，每个查询可以用四个整数 $a, b, x, y$ 表示。对于每个查询，你需要判断：是否对于每一个集合 $p$（$a \le p \le b$），该集合中都至少包含一条完全位于线段 $[x, y]$ 内的线段，即满足 $x \le l \le r \le y$。

请输出每个查询的答案。

注意：本题需要在线处理。也就是说，你只有在输出上一个查询的答案之后，才能收到下一个查询。

输入格式

• 第一行包含三个整数 $n, m, k$（$1 \le n, m \le 10^5$，$1 \le k \le 3 \cdot 10^5$）——分别表示集合的数量、查询的数量以及线段的总数。
• 接下来的 $k$ 行，每行包含三个整数 $l, r, p$（$1 \le l \le r \le 10^9$，$1 \le p \le n$）——表示线段的左右端点以及它所属的集合编号。
• 接下来的 $m$ 行，每行包含四个整数 $a, b, x, y$（$1 \le a \le b \le n$，$1 \le x \le y \le 10^9$）——表示一个查询。

输出格式

对于每个查询，输出一行 "yes" 或 "no"。

交互说明

在输出每个查询的答案后，不要忘记输出换行并刷新输出缓冲区，否则你会收到“Idleness limit exceeded”错误。具体方法如下：

• 在 C++ 中：fflush(stdout) 或 cout.flush()
• 在 Java 中：System.out.flush()
• 在 Pascal 中：flush(output)
• 在 Python 中：stdout.flush()
• 其他语言请参考对应文档。

样例

输入

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

输出

no
yes
yes
no
yes

样例解释

• 第一个查询：答案为 no，因为第 $2$ 个集合中没有完全位于 $[2, 3]$ 内的线段。
• 第二个查询：第 $1$ 个集合包含 $[2, 3]$，第 $2$ 个集合包含 $[2, 4]$。
• 第三个查询：第 $1$ 个集合包含 $[2, 3]$，第 $2$ 个集合包含 $[2, 4]$，第 $3$ 个集合包含 $[2, 5]$。
• 第四个查询：第 $2$ 个集合中没有完全位于 $[3, 6]$ 内的线段。
• 第五个查询：第 $2$ 个集合包含 $[2, 4]$，第 $3$ 个集合包含 $[2, 5]$，第 $4$ 个集合包含 $[7, 9]$。