这对 Katya 来说是非常重要的一天。她在编程课上进行了测试。和往常一样,她遇到了一个有趣的问题,她很快就解决了。你能解决这个问题吗?
您将获得 $$$n$$$ 有序段集。每个段可以表示为一对两个整数$$$[l, r]$$$,其中$$$l\leq r$$$。每个集合可以包含任意数量的段(甚至 $$$0$$$)。有些段可能是相等的。
您还会收到 $$$m$$$ 查询,每个查询都可以表示为四个数字:$$$a、b、x、y$$$。对于每个线段,找出每个集合 $$$p$$$ ($$$a\leq p\leq b$$$) 是否包含至少一个完全位于线段 $$$[x, y]$$$ 上的线段 $$$[l, r]$$$,即 $$$x\leq l\leq r\leq y$$$。
找出每个查询的答案。
注意,这个问题需要在线解决。也就是说,只有在打印上一个查询的答案后,您才会得到一个新的查询。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ $$$(1\leq n,m\leq 10^5, 1\leq k\leq 3\cdot10^5)$$$ - 分别是集合、查询和段的数量。
接下来的 $$$k$$$ 行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$p$$$ $$$(1\leq l\leq r\leq 10^9, 1\leq p\leq n)$$$ - 段的限制以及该段所属集合的索引。
接下来的 $$$m$$$ 行包含四个整数 $$$a, b, x, y$$$ $$$(1\leq a\leq b\leq n, 1\leq x\leq y\leq 10^9)$$$ — 查询的描述。
互动
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
输出
对于每个查询,在新行中打印“是”或“否”。
示例
输入 #1
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
输出 #1
no yes yes no yes
注意
对于第一个查询,答案是否定的,因为第二组不包含位于段 $$$[2, 3]$$$ 上的段。
在第二个查询中,第一组包含 $$$[2, 3]$$$,第二组包含 $$$[2, 4]$$$。
在第三个查询中,第一组包含 $$$[2, 3]$$$,第二组包含 $$$[2, 4]$$$,第三组包含 $$$[2, 5]$$$。
在第四个查询中,第二组不包含位于线段 $$$[3, 6]$$$ 上的线段。
在第五个查询中,第二组包含 $$$[2, 4]$$$,第三组包含 $$$[2, 5]$$$,第四组包含 $$$[7, 9]$$$。