Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3376
Safest Points

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Himekaidou Hatate (姫海棠はたて) is a crow tengu with the ability of spirit photography. The newspaper she writes, Kakashi Spirit News (「花果子念報」) is much less popular than Shameimaru Aya's Bunbunmaru News (「文々。新聞」). In order to beat Aya, Hatate decides to report Toramaru Shou, the disciple of Bishamonten (多闻天王). But it's not easy to take pictures of Shou and her bullet patterns while avoiding them as well.

Assum that both Hatate and Shou stay in a w*h grid region. Shou fire lasers out in straight lines, the i-th laser starts at (xi, yi) and moves in direction (dxi, dyi). The Manhattan distance of any two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|. Any point with a Manhattan distance to some laser that is less that 1 is called dangerous point. All other points are safe points. The points which have maximum Manhattan distance to dangerous points is called safest points. Hatate hopes that a new feature can be added to her camera - for each senario, finding out the safest points quickly. You're asked to develop this feature.

#### Input

There are multiple cases. Each one describes a senario. The first line is "w h n", where 3 ≤ w, h ≤ 1000 and 1 ≤ n ≤ 1000 is the number of lasers. The i+1-th line is the i-th laser "xi yi dxi dyi", where 0 ≤ xi < w, 0 ≤ yi < h, dxi2 + dyi2 > 0. Process to the each of file.

#### Output

For each case, output all safest points seperated by a single blank in lexicographic order. If there are no safe points, output "MISS!" instead.

```3 3 3
0 0 2 1
0 1 2 1
0 2 2 -2
4 4 2
0 0 3 3
3 0 -1 1
5 5 2
4 4 -1 -1
0 4 2 -2
```

#### Sample Output

```MISS!
(0, 1) (0, 2) (1, 0) (1, 3) (2, 0) (2, 3) (3, 1) (3, 2)
(0, 2) (2, 0) (2, 4) (4, 2)
```

#### Hint

 Sample I Sample II Sample III

#### References

Author: WU, Zejun
Source: ACM × Touhou
Contest: ZOJ Monthly, August 2010
Submit    Status