F. Катя и наборы отрезков
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кати сегодня важный день, у неё экзамен по программированию. Как всегда, ей дали интересную задачу и она легко с ней справилась. А справитесь ли вы с этой задачей?

Вам дано $$$n$$$ упорядоченных наборов из отрезков. Каждый отрезок может быть представлен как пара целых чисел $$$[l, r]$$$, где $$$l\leq r$$$. Каждый набор может содержать произвольное количество отрезков (даже $$$0$$$), возможно, что некоторые из них будут одинаковыми.

Также у вас есть $$$m$$$ запросов, каждый из которых в виде четырех целых чисел: $$$a, b, x, y$$$. Для каждого запроса вам нужно проверить верно ли, что в каждом наборе с номером $$$p$$$ ($$$a\leq p\leq b$$$), есть хотя бы один отрезок $$$[l, r]$$$, что целиком лежит на отрезке $$$[x, y]$$$, то есть $$$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)$$$ — описание запроса.

Выходные данные

Для каждого запроса в отдельной строке выведите ответ «yes», или «no».

Протокол взаимодействия

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
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
Примечание

Для первого запроса утверждение не истинно, поскольку второй набор не содержит отрезка что лежит в отрезке $$$[2, 3]$$$.

Для второго запроса первый набор содержит отрезок $$$[2, 3]$$$, а второй набор содержит отрезок $$$[2, 4]$$$.

В третьем запросе первому набору подходит отрезок $$$[2, 3]$$$, второму набору подходит отрезок $$$[2, 4]$$$, а третьему набору отрезок $$$[2, 5]$$$.

В четвертом запросе второй набор не содержит ни одного отрезка что лежит в отрезке $$$[3, 6]$$$.

В пятом запросе второму набору подходит отрезок $$$[2, 4]$$$, третьему набору подходит отрезок $$$[2, 5]$$$, а четвертому набору подходит отрезок $$$[7, 9]$$$.