描述

除其他外，计算分子生物学涉及处理基因序列。考虑到两个序列的进化关系，如果它们没有太大差异，我们可以说它们是密切相关的。我们可以用一棵树来表示这种关系，将来自祖先的序列放在其后代的序列之上。这样的树称为系统发育树。

虽然系统发育学的一项任务是从给定的序列中推断出一棵树，但我们将稍微简化并提供一个树结构 - 这将是一个完整的二叉树。您将获得树的 n 片叶子。当然你知道，n 总是 2 的幂。每片叶子都是一个氨基酸序列（由图中所示的单字符代码指定）。所有序列的长度均为相等 l。您的任务是以最低的成本推导出共同祖先的序列。

氨基酸丙氨酸AlaAArginineArgRAsparagineAsnNAspartic AcidAspDCysteineCysCGlutamineGlnQGlutamic AcidGluEGlycineGlyGHistidineHisHIsoleucineIleI

氨基酸亮氨酸LeuLLysineLysKMethionineMetMP

苯丙氨酸PheFProlineProPSerineSerSThreonineThrTTryptophanTrpWTyrosineTyrYValineValV

成本确定如下：树的每个内部节点都标有长度为 l 的序列，树的一条边的成本是边末端的两个序列不同的位置数，总成本是所有边的成本之和。然后在树的根处找到所有序列的共同祖先的序列。最佳公共上级是总成本最低的公共上级。

输入

输入文件包含多个测试用例。每个测试用例都以两个整数 n 和 l 开头，分别表示叶子处的序列数及其长度。Input 以 n=l=0 终止。否则，1<=n<=1024 和 1<=l<=1000。然后在氨基酸字母表上跟随长度为 l 的 n 个单词。它们从左到右表示完整二叉树的叶子。

输出

对于每个测试用例，输出一行，其中包含一些最佳公共上级和最小总成本。

输入数据 1

4 3
AAG
AAA
GGA
AGA

4 3
AAG
AGA
AAA
GGA

4 3
AAG
GGA
AAA
AGA

4 1
A
R
A
R

2 1
W
W

2 1
W
Y

1 1
Q

0 0

输出数据 1

AGA 3
AGA 4
AGA 4
R 2
W 0
Y 1
Q 0

来源

Ulm Local 2000