Looking for a Good Plot

A rich guy wants to buy some land to build a house. He is a bit eccentric and wants his parcel to have rectangular shape, with the sides aligned with earth’s meridians and parallels. Ideally, he would like a plot of land with a lake and, most importantly, with easy access by car. He does not care very much about money, hence he wants to buy the largest rectangular plot of land available which has access by car and contains a lake or is crossed by a river. If he cannot find a plot with both water and a road, he prefers one with only access by car rather than one with only water. However, he will conform with a plot without either one if nothing better is available. He has hired you to help him in his search. Your program will receive a map of an area. The map will be oriented with the north at the top. It will have to output the coordinates of the best plot available in the map, according to the following rules:

1. The plot must contain at least one square of available land, and may contain squares of water.
2. The plot must not contain any square of road or unavailable land.
3. The plot will be rectangular, with two sides aligned from north to south, and the other two sides aligned from west to east.
4. A plot which is adjacent to at least one square of road is considered to have easy access by car. We will consider that each square in the map has eight adjacent squares (that is: to the north, north-east, east, south-east, south, south-west, west and north-west). A plot with easy access by car is always better than another plot without it.
5. A plot that contains at least a square of water is better than a plot without water, unless the second plot has easy access by car and the first one doesn’t.
6. All the previous considerations being equal, the plot with the larger area is better than the smaller plot.
7. If the areas of two plots are the same and both have the same characteristics with respect to roads and water, the plot whose upper left corner is located more to the west is preferred; and if the upper left corners of both plots have the same longitude, the one more to the north is preferred. If both plots have the same area and the same coordinates for their upper left corners, the one which has its bottom right corner more to the east is preferred. Input The input format is as follows: An integer in a single line which indicates the number of maps that your program will have to process. Then, for each map there will be: • Two integers (w and h, both less than or equal to 500) in a single line which denote the width and height of the map. • h lines of w characters each. Each character represents a square of land, using the following notation:

2/2 Character: Meaning:

Unavailable land - Available land

###- -###

10 10 ####R----- ####R----- ####R--WW- #####R--W- ----##R--- -----##RRR ------##-- ------WWWW ----WWWWWW ----WWWWWW 33 WWW WWW WWW Sample Output 0041 6044 No good places.