Description

$\text{Bill}$ and $\text{Scott}$ are business rivals. They both plan to buy a house in the city of $\text{Javaville}$, but they want their homes to be as far away from each other as possible. Since $\text{Javaville}$ is a newly developed city, there is no map yet. Therefore, they can only collect information from local residents. This information includes the locations of buildings and the distances between buildings. Although the information is incomplete, it is all correct.

The streets of $\text{Javaville}$ form a rectangular grid, containing $m$ east-west streets labeled in order by capital letters $\text{A},\text{B},\text{C},\cdots$, and $n$ north-south streets labeled in order by numbers $0,1,2,\cdots$. We call the intersection of two streets an intersection, and a segment of street between two intersections a block. All buildings are located at intersections, and each intersection has at most one building. The distance between two buildings is defined as the minimum number of blocks that must be passed to get from one building to the other.

For example, $\text{Bill}$ and $\text{Scott}$ collected the following information:

• There are $5$ east-west streets and $5$ north-south streets in the city.
• House $1$ is located at intersection $A0$.
• The post office is located at intersection $A4$.
• The school is $4$ blocks away from house $1$.
• House $2$ is $6$ blocks away from the post office.
• The school is $6$ blocks away from the post office.
• House $3$ is $6$ blocks away from the post office.

Based on the above information, we can obtain two possible layouts of the city $\text{Javaville}$. We can see that the positions of house $1$, the post office, and the school are all determined, while house $2$ can be located at $C0$ or $E2$, and house $3$ can be located at $C0$ or $E2$. Therefore, there always exist two houses in the city that are $6$ blocks apart (in map $1$, $h1$ and $h3$; in map $2$, $h1$ and $h2$). However, for a fixed pair of houses, the longest distance we can guarantee is only $4$ blocks (the distance between $h2$ and $h3$ is always $4$ blocks). Thus, we should tell $\text{Bill}$ and $\text{Scott}$ that although there always exist two houses that are $6$ blocks apart, the safest suggestion is: one person buys house $2$, and the other buys house $3$.

Below is the strict definition of the required values:

• The diameter $d(S)$ of a feasible city layout $S$ is defined as the distance between the two farthest houses in that layout.

• For a fixed pair of houses $i, j$, their safety factor $e[i, j]$ is defined as the minimum distance between houses $i, j$ over all feasible city layouts.

$\text{Bill}$ and $\text{Scott}$ want you to write a program that, based on the information they collected, computes $D$ and $E$, where $D=\min\{d(S)\}$ and $E=\max\{e[i, j]\}$. You also need to output the safest house-buying suggestion, i.e. all houses $i, j$ such that $e[i, j]=E$.

For the example above, in the first layout $d(S_1)=6$, and in the second layout $d(S_2)=6$. The safety factors between each pair of houses are: $e[1,2]=2，e[1,3]=2，e[2,3]=4$. Therefore, $D=min{d(S1),d(S2)}=6，E= max{e[1,2],e[1,3],e[2,3]}=4$, and the safest house-buying suggestion is: house $2$ and house $3$.

Input Format

The first line contains two positive integers $m, n（1\le m, n\le 10）$, representing the number of east-west streets and north-south streets, respectively. The second line contains an integer, representing the number of collected pieces of information $t(1\le t\le 50)$. Starting from the third line, each line describes one piece of collected information, and each piece is in one of the following two forms:

• name LOCATION r c

or

• name DISTANCE d name2

These two forms describe the location of a building and the distance between two buildings, respectively.

Here, $\text{name}$ and $\text{name2}$ are strings containing only digits and lowercase letters, with length at most $20$, representing building names. $r$ is a capital letter between $\text{A}$ and $\text{J}$, and $c$ is a digit, indicating the intersection where the building is located. $d$ is a positive integer, indicating the distance between the two buildings. If the first five characters of a building name are the lowercase letters $\text{“house”}$, then it is a purchasable house; otherwise, it is a non-residential building. If the information is of the second form, then $\text{name2}$ must have appeared in the earlier information.

This set of information contains at least two purchasable houses, and at most $25$ different buildings in total.

Output Format

The first line contains two integers, representing $D$ and $E$, separated by one space.

5 5
6
house1 LOCATION A 0
postoffice LOCATION A 4
school DISTANCE 4 house1
house2 DISTANCE 6 postoffice
school DISTANCE 6 postoffice
house3 DISTANCE 6 postoffice

6 4

Hint

All Constraints are mentioned in the input format.

Translated by ChatGPT 5