Bill and Scott are business rivals. Each of them wishes to buy a house in Javaville, but they want to live as far away from eachother as possible. Since Javaville is a relatively new town, there areno maps available yet; instead, information about homes and other buildings has been collected by word of mouth and provided to both Bill and Scott. This information consists of building addresses and distances between buildings. All of the information is consistent, although it may be incomplete or redundant.

The streets in Javaville are laid out in a rectangular grid of m east/west streets (named ‘A ’, ‘B ’, ‘C ’, …) and n  north/south streets (numbered ‘0 ’, ‘1 ’, 2 ’, …), where m  and n  are each between 2 and 10. Every building (either a house or some other building, such as a post office or school) in Javaville is at the intersection of two streets, and no two buildings are located at the same intersection. Some intersections have no buildings at all. All distances are measured in terms of the smallest number of whole blocks that must be traversed north, south, east, and/or west to get from one intersection to another intersection.

Here is some sample information that might be provided to Bill and Scott by various reliable sources:

– There are 5 east/west streets and 5 north/south streets.

– House1 is located at intersection A0

– The post office is located at intersection A4

– The school is at a distance of 4 blocks from house1

– House2 is at a distance of 6 blocks from the post office

– The school is at a distance of 6 blocks from the post office

– House3 is at a distance of 6 blocks from the post office

From this we can see that there are two possible maps of Javaville — see Figure 1.

Figure 1: h1,h2,h3 = houses, P = postoffice, S = school

We see that the locations of house1, the post office, and the school are fixed, but house2 could beat either C0  or E2 , and house3 could be at either C0  or E2 . Clearly there is always a pair of housesseparated by 6 blocks (house1 is always 6 blocks from the furthest house), but the best distance wecan guarantee for any specific pair  of houses is 4 (since house2 is always 4 blocks away from house3). We would report this information to Bill and Scott, telling them that, even though a separation of 6 is always achievable, the safest recommendation that we are able to make for specific houses is to have one of them purchase house2 and have the other purchase house3. (We assume that Bill and Scott will consult with one another before purchasing their houses in order to guarantee that one of our recommendations is followed.)

Bill and Scott would like you to write a program that will take location and distance information about buildings and determine two quantities, D  and D′ . D  is the minimum, over all possible valid arrangements of buildings, of the largest house separation in each arrangement. D′  is the maximum value for which there exists at least one pair of houses i  and j  that are guaranteed to be separated by a distance of at least D′ . In the latter case, you should list all pairs of houses that are guaranteed to be separated by at least D′  blocks.

More precisely,

Define the diameter d(S) of a feasible urban layout S as the distance between the two most distant residential homes in the layout. For the two residential houses i, j, define their safety factor: e[i, j] is defined as the minimum value of the distance between residential houses i and j in all feasible urban layouts. Bill and Scott want you to write a program that calculates D and D' based on the information they collect, where

D = min {d (S)} over all layouts S;
D' = max {e [i, j]} over all pairs (i, j).

At the same time you also have to give the safest purchase recommendations: that is, all pairs (i,j) meeting e [i, j] = D' for residential houses i and j.
For the above example, the first layout has d (S1) = 6, while the second layout has d (S2) = 6. The safety factor between each two residential houses is respectively:

e [1,2] = 2, e [1,3] = 2, e [2,3] = 4. Then,
D = min {d (S1), d (S2)} = 6, and
D' = max {e [1,2], e [1,3], e [2,3]} = Purchase recommendations are: house 2 and house 3.

The diameter d (S) of a feasible urban layout S is defined as the distance between the two most distant homes in the layout.
For the two residential buildings i, j, their safety factor e [i, j] is defined as the minimum value of the distance between residential i and j in all feasible urban layouts.
Bill and Scott want you to write a program that calculates D and E based on the information they collect. Where D = min {d (S)}; E = max {e [j, j]}. At the same time you have to give the safest purchase recommendations, that is, all meet e [i, j] = E residential i, j.
For the above example, the first layout of d (S1) = 6, the second layout of d (S2) = 6. The safety factor between each two dwellings is: e [1,2] = 2, e [1,3] = 2, e [2,3] = 4. Then, D = min {d (S1), d (S2)} = 6, E = max {e [1,2], e [1,3], e [2,3]} = Purchase recommendations are: residential 2 and residential 3.

### Input

The input will consist of one or more descriptions. Each description will begin with a line containing two positive integers, m  and n , representing the number of blocks in each direction (2 ≤ m, n ≤10 ).  Each description will end with a line containing the single word ‘END’ in uppercase. The entire data set will end with a line containing a pair of zeros.

The remaining lines in each data set will be in one of the following two formats:

name LOCATION r c

or

name DISTANCE d name2

where name  and name2  are strings containing only digits and lowercase alphabetic characters, each of length at most 10; r is an uppercase letter between ‘A ’ and ‘J ’; c  is a digit; and d is a positive integer.  If the first five characters of a name  are the lowercase letters ‘house ’ then it is a candidate for selection as a home for Bill or Scott; otherwise it stands for some non-residential building. In a ‘DISTANCE’ specification, name2 will always be the name of some building that has occurred previously in this data set as the first name  on one of the data lines (in other words, there are no forward references to buildings in ‘DISTANCE’ constraints). Each description is consistent (i.e., there is at least one way to lay out the houses and other buildings in a way consistent with the description). Each description will include information about at least two distinct houses. At most 25 distinct building names will occur in each description, and there will be at most 50 constraints (‘LOCATION’ or ‘DISTANCE’) for each description.

### Output

For each description, the output will consist of D, followed by value of D', and then a list of all pairs of houses with maximum guaranteed separation D′  (which might be smaller than the maximum achievable separation). No pair of houses should be listed more than once. The output should be labeled exactly as shown in the sample output below, with a blank line separating the outputs for consecutive data sets. In each pair, houses should be ordered according to the first time they appear in the input; the list of pairs should be ordered in the same way, sorted by the first element of the pair, then by the second element.

### Example

```Input:
5 5house1 LOCATION A 0postoffice LOCATION A 4school DISTANCE 4 house1house2 DISTANCE 6 postofficeschool DISTANCE 6 postofficehouse3 DISTANCE 6 postofficeEND10 10house1 LOCATION A 0building2 DISTANCE 12 house1building2 DISTANCE 12 house1house3 DISTANCE 7 house1building4 DISTANCE 2 house3building4 DISTANCE 7 building2building4 DISTANCE 2 house3house5 DISTANCE 6 building4building6 DISTANCE 10 building2building6 DISTANCE 5 building4building6 DISTANCE 2 house1house7 DISTANCE 1 house1house7 DISTANCE 1 house1building8 DISTANCE 10 house7house9 DISTANCE 10 building2house9 DISTANCE 3 building4building10 DISTANCE 5 house3building10 DISTANCE 5 house3house11 DISTANCE 3 building2building12 DISTANCE 7 house7building12 DISTANCE 8 house1building12 DISTANCE 9 building4building12 DISTANCE 3 house5house13 DISTANCE 7 building8house13 DISTANCE 3 house5building14 DISTANCE 2 building10building14 DISTANCE 9 building8house15 DISTANCE 12 building8house15 DISTANCE 11 building12house15 DISTANCE 9 building2house15 DISTANCE 7 house13building16 DISTANCE 6 building10building16 DISTANCE 3 house11building16 DISTANCE 12 house9building16 DISTANCE 5 house7house17 DISTANCE 4 house11house17 DISTANCE 3 building12building18 DISTANCE 8 building14building18 DISTANCE 10 building6building18 DISTANCE 8 building14building18 DISTANCE 10 building6house19 DISTANCE 2 house13house19 DISTANCE 6 building18house19 DISTANCE 1 house5building20 DISTANCE 8 building14END0 0```
`Output:6 4house2 house39 9house1 house11house5 house9house9 house11house9 house17`