| VK Cup 2015 - Раунд 1 |
|---|
| Закончено |
У Поликарпа есть шахматная доска размера n × m, на которой расставлены k ладей. Поликарп еще не придумал правила игры, в которую он будет играть. Однако он уже выделил на доске q прямоугольных участков особой стратегической важности, которые должны быть надежно защищены. По мнению Поликарпа, прямоугольный участок доски надежно защищен, если все его свободные клетки бьются ладьями, стоящими на этом участке. Ладьи на остальной части доски на защиту участка не влияют. Расстановка ладей фиксирована и не может быть изменена. Напомним, что ладья бьет все клетки, расположенные с ней на одной вертикали или горизонтали, если между клеткой и ладьей нет других фигур. Помогите Поликарпу определить, все ли стратегически важные участки надежно защищены.
В первой строке содержатся четыре целых числа n, m, k и q (1 ≤ n, m ≤ 100 000, 1 ≤ k, q ≤ 200 000) — размеры доски, количество ладей и количество стратегически важных участков. Будем считать, что клетки доски пронумерованы числами от 1 до n по горизонтали и от 1 до m по вертикали. Следующие k строк содержат пары целых чисел «x y», описывающие положение ладей (1 ≤ x ≤ n, 1 ≤ y ≤ m). Гарантируется, что все ладьи стоят в разных клетках. Следующие q строк описывают стратегически важные участки четверками чисел «x1 y1 x2 y2» (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m). Соответствующий прямоугольный участок состоит из клеток (x, y), для которых x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. Стратегически важные участки могут пересекаться или совпадать.
Выведите q строк. Для каждого стратегически важного участка выведите «YES», если он надежно защищен, и «NO» в противном случае.
4 3 3 3
1 1
3 2
2 3
2 3 2 3
2 1 3 3
1 2 2 3
YES
YES
NO
Рисунок к примеру: 
Для последнего участка ответ «NO», потому что клетка (1, 2) не бьется ладьей.
