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