Welcome to ZOJ
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.

Sample Input

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 image for sample I
Sample II image for sample II
Sample III image for sample III

References

上海アリス幻樂団

acm_x_touhou


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