Secure Region

Time limit1sMemory limit128 MB

Summary

Given an axis-aligned field and up to 300 mines, find the axis-aligned mine-free rectangle with the largest shorter side, then the largest longer side.

Level: Hard8 of 10
Topics: Geometry, Binary search, Sorting, Brute force
Solved: No attempts yet

Problem

A minefield is given as an axis-aligned bounding rectangle together with the positions of all mines inside it. A helicopter must land on the most secure region: an axis-aligned rectangle that lies within the field, contains no mine in its interior, and whose shorter side is as long as possible.

Formally, consider every axis-aligned rectangle inside the field that contains no mine in its interior. Let its side lengths be $A$ and $B$ with $A \le B$ . The most secure region is the one with the largest possible $A$ ; among all rectangles achieving that largest $A$ , it is the one with the largest $B$ .

A mine lying exactly on an edge or corner (the boundary) of a rectangle does not count as being inside it.

Given the bounding rectangle of the field and the positions of all mines, compute the two side lengths of the most secure region.

Input

The input consists of several minefields.

Each minefield is described as follows. The first line contains four integers $X_1$ , $Y_1$ , $X_2$ , $Y_2$ , where $(X_1, Y_1)$ is the lower-left corner and $(X_2, Y_2)$ the upper-right corner of the field ( $-20000 \le X_1 < X_2 \le 20000$ and $-20000 \le Y_1 < Y_2 \le 20000$ ). The next line contains an integer $N$ ( $1 \le N \le 300$ ), the number of mines. Each of the following $N$ lines contains two integers $X$ and $Y$ , the position of a mine ( $X_1 \le X \le X_2$ and $Y_1 \le Y \le Y_2$ ). No two mines share the same position.

The input ends with a line where $X_1 = Y_1 = X_2 = Y_2 = 0$ ; this line is not processed.

Output

For each minefield, print one line with two integers $A$ and $B$ ( $A \le B$ ): the two side lengths of the most secure region.

Examples3

Example 1

Input

0 0 100 100
9
0 0
0 100
100 0
100 100
50 50
25 50
50 25
75 50
50 75
-2 0 6 8
3
0 2
2 4 
4 6 
0 0 0 0

Expected output

50 50
4 6

Example 2
Input
```
0 0 10 10
1
5 5
0 0 0 0
```
Expected output
```
5 10
```
Example 3
Input
```
0 0 20 10
1
5 5
0 0 0 0
```
Expected output
```
10 15
```