Matcom Online Grader

You have been hired by Mines Never Again, a non-governmental organization whose aim is to ban the use of landmines. Besides working on political aspects, such as lobbying governments to join the International Campaign to Ban Landmines, MNA also works on disarming mines left by past wars.

Nowadays, mines are detected by satellites or surveillance airplanes. But to disarm a mine you have to get close to it. In most cases, the only way to reach a mined field is by helicopter. To clear the field, you must find the most secure region within the field so that the helicopter can land on it. This region is a rectangle with sides parallel to the coordinate axes, with no mines inside and whose smaller side is the largest possible. More precisely, let $A$ and $B$ be the length of the sides of all possible rectangles that do not contain any mines and $A \leq B$; the most secure region is a rectangle with the largest value of $A$ and the largest value of $B$. That is, among all rectangles that do not contain any mines and whose smaller side is $A$ (largest possible), the most secure region is a rectangle that has the largest $B$.

Given the limiting rectangle of a mined field and the positions of all mines inside the field, you must write a program to find the size of the most secure region.

Your program should process data for several mined fields. The first line of a mined field contains four integers $X_1$, $Y_1$, $X_2$ and $Y_2$ which bound the field. $(X_1, Y_1)$ are the coordinates of the field’s lower left corner, $(X_2, Y_2)$ are the coordinates of the field’s upper right corner ($-20000 \leq X_1 \lt X_2 \leq 20000$ and $-20000 \leq Y_1 \lt Y_2 \leq 20000$). The second line contains a single integer N indicating the number of mines detected in the field $(1 \leq N \leq 300)$. The following $N$ lines contain each two integers $X$ and $Y$ describing the position of a mine ($X_1 \leq X \leq X_2$ and $Y_1 \leq Y \leq Y_2$). No two mines have the same location. The end of input is indicated when $X_1 = Y_1 = X_2 = Y_2 = 0$.

For each mined field of the input your program should print a line with two integers $A$ and $B$, where $A \leq B$, describing the size of the most secure region.