Doggone Moles

A mole has riddled our yard with a rectangular grid of tunnels. Furious at the damage, we release several terriers into the yard to catch it. The terriers have very sensitive hearing: if they get close enough to the mole, they can dig quickly and catch it. Unfortunately, the mole is also very sensitive to the vibrations of the terriers' footsteps, and it actively tries to evade them.

We do not know where the mole was when the terriers were released. But we have watched the terriers move around the yard for some time, and the mole has not been caught. Write a program that deduces where the mole might be, given our observations.

At the moment we began recording, we also know the mole was not directly beneath a terrier, nor in a cell adjacent (horizontally or vertically) to one. In each following time interval, the terriers may stay put or move one cell horizontally or vertically; then the mole may do the same. If at any point — before or after any of these moves, whether by a terrier or by the mole — a terrier ends up directly over the mole or in a cell adjacent (horizontally or vertically) to it, the mole is caught.

Given a description of the yard and the terriers' positions over a period of time, print every cell where the mole could still be at the end of that period.

The input consists of one or more observation sets. Each set is given as follows:

• The first line contains four integers W L N T. W and L are positive integers: the width (x dimension) and length (y dimension) of the yard. N is the number of terriers (non-negative). T is the number of observed time steps (positive).
• The next N lines each describe one terrier. A line contains 2T integers: the (x, y) coordinates of that terrier at each of the T time steps, separated by whitespace with no parentheses or commas. Coordinates range from (0, 0) at one corner of the yard to (W, L) at the opposite corner.

The end of the input is signalled by a line of four zeros in place of a valid W L N T line.

For each observation set, print a line Observation Set k, where k is the number of the set (starting at 1).

If there is at least one possible location for the mole, then on the following lines print all possible locations as (x,y) pairs, at most 8 pairs per line (the last line for a set may have fewer). Print no leading blanks before the first pair on a line and no trailing blanks after the last pair; separate consecutive pairs on the same line by exactly one blank. Each pair is written as (x,y) with no internal blanks. Order the pairs so that smaller y comes first, and among pairs with equal y, smaller x comes first.

If there are no possible locations, then the second line of output for the set is the message No possible locations.

A sample scenario can be visualized as follows: