Андрійко напився дуже багато компотику, і тепер він дуже боїться прямокутників. Кімнату Андрійка можна математично представити як прямокутник висотою 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≤n,m≤106,1≤k≤5000)
Кожен з наступних k рядків містить чотири цілі числа x1, y1, x2, y2 (0≤x1≤x2≤n;0≤y1≤y2≤m) — координати верхнього лівого та правого нижнього кутів прямокутника i.
Гарантується, що жоден прямокутник не дотикається до точок (0,0) та (n,m).
Виведіть «YES
», якщо Андрійко може пройти між кінцями кімнати, і «NO
» — інакше.
(3 бали): k=1
(4 бали): k=2
(5 балів): k=3
(17 балів): 1≤k≤50
(26 балів): 1≤k≤1000
(20 балів): 1≤n,m≤5000
(25 балів): Без додаткових обмежень