Bill and Scott are business rivals. They both plan to buy a house in the city of Javaville, but they want their houses to be as far apart as possible. Since Javaville is a newly emerging city, there is no map yet. They can only collect information from the locals, including the locations of buildings and the distances between them. Although this information is incomplete, it is accurate.

The streets of Javaville form a rectangular grid, containing $m$ east-west streets, labeled with uppercase letters $A, B, C, \dots$, and $n$ north-south streets, labeled with numbers $0, 1, 2, \dots$. The intersection of two streets is called a junction, and the segment of a street between two junctions is called a block. All buildings are located at junctions, and each junction contains at most one building. The distance between two buildings is defined as the minimum number of blocks required to travel from one building to another.

For example, Bill and Scott collected the following information: There are 5 east-west streets and 5 north-south streets in the city; house1 is located at junction $A0$; postoffice is located at junction $A4$; The distance between school and house1 is 4 blocks; The distance between house2 and postoffice is 6 blocks; The distance between school and postoffice is 6 blocks; * The distance between house3 and postoffice is 6 blocks;

Figure 1: h1, h2, h3 = houses, p = post office, s = school

Based on the above information, we can derive two possible layouts for the city of Javaville. We find that the locations of house1, the post office, and the school are already determined, while house2 can be located at $C0$ or $E2$, and house3 can be located at $C0$ or $E2$. Thus, there are always two houses in the city that are 6 blocks apart ($h1$ and $h3$ in map 1, $h1$ and $h2$ in map 2). However, for any two specific houses, we can only guarantee a maximum distance of 4 blocks (the distance between $h2$ and $h3$ is always 4 blocks). Therefore, we must tell Bill and Scott that although there are always two houses 6 blocks apart, the safest recommendation is: one person buys house2, and the other buys house3.

The strict definitions of the required values are as follows: The diameter $d(S)$ of a feasible city layout $S$ is defined as the distance between the two furthest houses in that layout. For two specific houses $i, j$, their safety factor $e[i, j]$ is defined as the minimum distance between house $i$ and house $j$ across all feasible city layouts.

Bill and Scott want you to write a program to calculate $D$ and $E$ based on the information they collected, where $D = \min\{d(S)\}$ and $E = \max\{e[i, j]\}$. You must also provide the safest house-buying recommendations, which are all pairs of houses $i, j$ that satisfy $e[i, j] = E$.

Input

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 $t$ ($1 \le t \le 50$), representing the number of pieces of information collected. Starting from the third line, each line describes one piece of information in one of the following two formats:

name LOCATION r c or name DISTANCE d name2

These two formats describe the location of a building and the distance between buildings, respectively. Here, name and name2 are strings containing only digits and lowercase letters, with a length not exceeding 20, representing the names of the buildings. $r$ is an uppercase letter from $A$ to $J$, and $c$ is a number, representing the junction where the building is located. $d$ is a positive integer representing the distance between two buildings. If the first five characters of the building name are "house", it represents a house that can be purchased; otherwise, it represents a non-residential building. If the information is in the second format, name2 must have appeared in previous information.

This set of information contains at least two houses that can be purchased and at most 25 different buildings.

Output

The first line contains two integers, $D$ and $E$, separated by a space. Starting from the second line, output all the safest house-buying recommendations, with each recommendation on a new line. The recommendations can be listed in any order, but there must be no duplicates. There should be no trailing spaces at the end of each line.

Examples

Input 1

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

Output 1

6 4
house2 house3