Прямокутники всюди
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Андрійко напився дуже багато компотику, і тепер він дуже боїться прямокутників. Кімнату Андрійка можна математично представити як прямокутник висотою $$$n$$$ і шириною $$$m$$$. У цій кімнаті є $$$k$$$ прямокутників, кожен з яких повністю лежить у кімнаті й не торкається точок $$$(0,0)$$$ та $$$(n,m)$$$, точка $$$(0,0)$$$ - ліва верхня, $$$(n,m)$$$ - права нижня.

Андрійко хоче прийти з кута $$$(0,0)$$$ в кут $$$(n,m)$$$, жодного разу не опиняючись у жодному з $$$k$$$ прямокутників (навіть не торкаючись їх). Якщо він перебуває в координаті $$$(x, y)$$$, то за один крок він може переміститися у будь-яку з наступних координат: $$$(x-0.5, y)$$$, $$$(x+0.5, y)$$$, $$$(x, y-0.5)$$$, $$$(x, y+0.5)$$$, але лише за умови, що наступна координата не виходить за межі прямокутника. Визначте, чи зможе він дійти від одного кута до іншого.

Вхідні дані

Перший рядок містить три цілі числа $$$n$$$, $$$m$$$, $$$k$$$ $$$(1 \le n,m \le 10^6, 1 \le k \le 5\,000)$$$

Кожен з наступних $$$k$$$ рядків містить чотири цілі числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ $$$(0 \le x_1 \le x_2 \le n; 0 \le y_1 \le y_2 \le m)$$$ — координати верхнього лівого та правого нижнього кутів прямокутника $$$i$$$.

Гарантується, що жоден прямокутник не дотикається до точок $$$(0,0)$$$ та $$$(n, m)$$$.

Вихідні дані

Виведіть «YES», якщо Андрійко може пройти між кінцями кімнати, і «NO» — інакше.

Система оцінки

  1. ($$$3$$$ бали): $$$k = 1$$$
  2. ($$$4$$$ бали): $$$k = 2$$$
  3. ($$$5$$$ балів): $$$k = 3$$$
  4. ($$$17$$$ балів): $$$1 \le k \le 50$$$
  5. ($$$26$$$ балів): $$$1 \le k \le 1000$$$
  6. ($$$20$$$ балів): $$$1 \le n,m \le 5000$$$
  7. ($$$25$$$ балів): Без додаткових обмежень

Приклади

Вхідні дані
3 4 3
0 2 1 4
1 2 3 3
2 1 3 3
Вихідні дані
NO
Вхідні дані
3 4 3
0 2 1 4
1 0 2 1
2 1 3 3
Вихідні дані
YES