Shelob's Lair

Sam Gamgee and Frodo Baggins are trapped in Shelob's lair. Shelob is a giant spider that lives in the caves on the edge of Mordor.

The lair is one large rectangular cavern, and Shelob has spun many webs across it. Sam and Frodo stand at the south wall and have to reach the north wall to escape. If either of them touches a web, he sticks to it and Shelob comes to eat them.

Sam carries Sting, a sword that cuts through Shelob's web. Frodo is poisoned and Sam is worn out from the journey, so Sam has the strength for exactly one vertical slice. A slice at a chosen point cuts every web that passes through that point, and the hobbits squeeze through the slit. Only that single point disappears from a web that was cut. The rest of it stays where it is and still blocks the way, so the route the hobbits walk may meet the webs at that one point and nowhere else.

Each web is a vertical sheet running from one point to another. It is fixed to the floor and the roof of the cave and runs in a straight line between its two ends, so seen from above it is a line segment. Shelob spins well, so webs cross one another, and a slice at a crossing point cuts every web through that point at once. No web touches the north wall or the south wall. Sam can also cut exactly at a point where one or more webs meet the east wall or the west wall. Treat Sam and Frodo as a single point: they fit through the slit, and they fit between two webs that do not touch.

Given the positions of all the webs, decide whether the hobbits can reach the north wall with at most one slice.

The input contains one test case.

The first line has three integers $w$, $d$, and $n$: the width of the cave, the depth of the cave, and the number of webs, with $1 \le w, d \le 1000$ and $1 \le n \le 500$.

Each of the next $n$ lines has four integers $x_1$, $y_1$, $x_2$, $y_2$, with $0 \le x_1, x_2 \le w$ and $0 < y_1 < d$, $0 < y_2 < d$. The points $(x_1, y_1)$ and $(x_2, y_2)$ are the two ends of one web. The south-west corner of the cave is $(0, 0)$ and the north-east corner is $(w, d)$.

If the hobbits can reach the north wall with at most one slice, print the line

We can make it Mr Frodo!

Otherwise print the line

We're doomed Mr Frodo!