Doors and Penguins

The organizers of a large computing conference have invited several vendors to set up booths in a big exhibition hall to showcase their latest products. After the booths were assigned and built, the organizers realized an important detail: each vendor supports exactly one of two operating systems — Doors or Penguins — never both, and a vendor supporting one system does not want a booth next to a vendor supporting the other.

The booths have already been placed and cannot be moved or reassigned. To keep the two groups apart, the organizers have portable partition screens that can build a single straight wall of any length. The wall must not touch any booth (it may come arbitrarily close to touching one). Determine whether the two groups of vendors can be separated by one such straight wall.

The input contains several test cases.

Each case begins with a line holding two integers $D$ and $P$ separated by a single space: the number of vendors supporting Doors and the number supporting Penguins, respectively ($1 \le D, P \le 500$).

The next $D$ lines describe the Doors booths, followed by $P$ lines describing the Penguins booths. Each booth is given by four positive integers $x_1\ y_1\ x_2\ y_2$, where $(x_1, y_1)$ is the south-west corner and $(x_2, y_2)$ is the north-east corner, with $x_1 < x_2$ and $y_1 < y_2$. Every booth is an axis-parallel rectangle.

The exhibition hall has its south-west corner at $(0, 0)$ and its north-east corner at $(15000, 15000)$. All booths lie strictly inside the hall and do not touch its walls. No two booths overlap or touch each other.

The input ends with a line containing $D = P = 0$, which is not processed.

For each case, print the case number (starting from 1) followed by a colon and a space, then print

It is possible to separate the two groups of vendors.

if the two groups can be separated by a single straight wall, or

It is not possible to separate the two groups of vendors.

otherwise. Print a blank line between consecutive cases.