Прямокутники всюди#190

Прямокутники всюди

1 секунда

256 мегабайтів

Середня

Андрійко напився дуже багато компотику, і тепер він дуже боїться прямокутників. Кімнату Андрійка можна математично представити як прямокутник висотою $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 + 0.5, y)$ (x+0.5, y), $(x, y - 0.5)$ (x, y-0.5), $(x, y + 0.5)$ (x, y+0.5), але лише за умови, що наступна координата не виходить за межі прямокутника.

Визначте, чи зможе він дійти від одного кута до іншого.

Вхідні дані

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

Кожен з наступних $k$ рядків містить чотири цілі числа $x_{1}$ x_1, $y_{1}$ y_1, $x_{2}$ x_2, $y_{2}$ y_2 $(0 \leq x_{1} \leq x_{2} \leq n; 0 \leq y_{1} \leq y_{2} \leq m)$ (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

Приклад 2

Оцінювання

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