House Selection in Javaville

Bill and Scott are business rivals who plan to purchase a house in the emerging city of Javaville. The city is arranged in a rectangular grid with m east-west streets labeled A, B, C, … and n north-south streets labeled 0, 1, 2, …. Every building is located at an intersection (with at most one building per intersection) and the distance between two buildings is defined as the minimum number of street blocks one needs to traverse (i.e. the Manhattan distance).

Some of the information collected is incomplete. For certain buildings the exact location is known (e.g. House1, PostOffice), while for others (like some residences) only additional distance constraints are provided. For example, you may know that:

• There are 5 east‐west streets and 5 north‐south streets.
• House1 is located at A0.
• The PostOffice is located at A4.
• The School is 4 blocks away from House1 and 6 blocks away from the PostOffice.
• House2 and House3 are each 6 blocks away from the PostOffice.

From the above, some building locations (like House1, PostOffice and even School) will be uniquely determined while others (such as House2 and House3) may have more than one valid candidate position. In fact, in the sample, House2 and House3 can only be located at C0 or E2 with the restriction that they must occupy distinct intersections. Consequently, there are exactly two feasible city layouts:

1. Layout 1: House1 at A0, House2 at C0, House3 at E2 (with d(S)=6, where d(S) is the maximal Manhattan distance among any two residences).
2. Layout 2: House1 at A0, House2 at E2, House3 at C0 (again with d(S)=6).

For any pair of residences i and j, define their safety coefficient \(e[i,j]\) as the minimum Manhattan distance between them over all feasible layouts. In the sample, \(e[House1,House2]=2\), \(e[House1,House3]=2\), while \(e[House2,House3]=4\). We then define:

• \(D = \min\{d(S)\}\), the minimum possible diameter among all feasible layouts.
• \(E = \max\{e[i,j]\}\), the best (largest) guaranteed minimum distance between some pair of residences.

In the example, although there always exist two residences at distance 6 in each layout, the best guarantee is only 4 blocks (between House2 and House3). Your task is to compute D and E and also output all unordered pairs of residences \(i,j\) for which \(e[i,j]=E\).

---

Note: All formulas must be expressed in LaTeX format. For example, the Manhattan distance is defined as \(d((x_1,y_1),(x_2,y_2)) = |x_1-x_2|+|y_1-y_2|\).

inputFormat

The input consists of multiple sections:

1. The first line contains two integers m and n representing the number of east-west and north-south streets respectively.
2. The next line contains an integer b indicating the number of buildings. Then follow b lines. Each line contains three tokens:
   • BuildingID (e.g. House1, PostOffice, School)
   • Type (either residence or landmark)
   • Position: either the fixed coordinate in the format LetterNumber (e.g. A0, A4) or a single dash '-' if the position is not fixed.
3. The next line contains an integer p representing the number of distance constraints. Each of the following p lines contains a constraint in the format:
   BuildingID1 BuildingID2 d
   indicating that the Manhattan distance between BuildingID1 and BuildingID2 is exactly d blocks. (Each constraint is symmetric.)

outputFormat

The output should consist of:

1. The first line contains two integers D and E separated by a space.
2. For each unordered pair of residences \(i,j\) for which \(e[i,j] = E\), output a line with the two BuildingIDs (separated by a space). Each pair should be listed only once (order does not matter).

sample

5 5
5
House1 residence A0
House2 residence -
House3 residence -
PostOffice landmark A4
School landmark -
4
House1 School 4
House2 PostOffice 6
School PostOffice 6
House3 PostOffice 6

6 4
House2 House3

</p>