#102546. [BZOJ 2546] [Ctsc2002]购房计划

Bill 和 Scott 是商业对手。他们都计划在 Javaville 城市购买一幢房子，但是他们希望自己的住宅尽量远离对方的住宅。由于 Javaville 是一座新兴的城市，所以暂时还没有地图，于是，他们只能从当地人的口中搜集信息，这些信息包括建筑物的位置和建筑物之间的距离。尽管这些信息并不完整，但是它们都是正确的。

Javaville 的街道是一个矩形网格，包含 条东西走向的街道，依次用大写字母 标识， 条南北走向的街道，依次用数字 标识。我们把两条街道的交点称为交叉路口，两个交叉路口之间的一段街道称为街区。所有的建筑物都位于交叉路口处，每个交叉路口至多只有一座建筑物。建筑物之间的距离定义为从一座建筑物到另一座建筑物所需经过的最少的街区数。

例如，Bill 和 Scott 搜集了以下这些信息：

• 城市中有 条东西走向的街道和 条南北走向的街道；
• 住宅 位于交叉路口 ；
• 邮局位于交叉路口 ；
• 学校与住宅 距离 个街区；
• 住宅 与邮局距离 个街区；
• 学校与邮局距离 个街区；
• 住宅 与邮局距离 个街区；

根据以上信息，我们可以得到 Javaville 城市可能的两种布局。我们发现：住宅 、邮局和学校的位置都已经确定了，而住宅 可以位于 或 ，住宅 可以位于 或 。于是，城市中总是存在两座住宅相距 个街区（地图 1 中的 与 ，地图 2 中的 与 ）。但是，对于确定的两座住宅，我们可以保证的最长距离只有 个街区（ 与 的距离总是 个街区）。于是，我们要告诉 Bill 和 Scott，尽管总是存在两座相距 个街区的住宅，然而最安全的建议是：一人购买住宅 ，另一人购买住宅 。

下面给出所求数值的严格定义：

• 一个可行的城市布局 的直径 定义为该布局中距离最远的两座住宅之间的距离。
• 对于确定的两座住宅 ，它们的安全系数 定义为在所有可行的城市布局中，住宅 之间的距离的最小值。

Bill 和 Scott 希望你编写一个程序，根据他们所搜集到的信息，计算出 和 。其中：，。同时你还要给出最安全的购房建议，即所有满足 的住宅 。

对于上面的例子，第一种布局的 ，第二种布局的 。每两座住宅之间的安全系数是：，，。于是：，，最安全的购房建议是：住宅 与住宅 。

第一行包含两个正整数 （），分别表示东西走向的街道数目和南北走向的街道数目。第二行包含一个整数，表示所搜集到的信息条数 （）。

文件从第三行开始每行描述一条所搜集到的信息，每条信息都是 或者 两种形式之一。

这两种形式分别描述建筑物的位置和建筑物之间的距离。

其中， 和 是仅包含数字和小写字母的字符串，长度不超过 ，表示建筑的名称。 是 到 之间的大写字母， 是一个数字，表示建筑物所位于的交叉路口。 是一个正整数，表示两座建筑物之间的距离。如果建筑物名称的前五个字符是小写字母 house，那么表示这是一座可以购买的住宅，否则表示一座非民用的建筑物。如果信息是第二种形式，那么其中的 一定在前面的信息中出现过。

这组信息中至少包含两座可以购买的住宅，至多包含 座不同的建筑物。

第一行包含两个整数，分别表示 和 ，之间用一个空格隔开。

样例输入 #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

样例输出 #1

6 4