题目描述

现在是季前赛阶段，当地报纸想要发布一份本地业余篮球联赛各球队的季前赛排名。这些球队分别是蚂蚁队（the Ants）、桶队（the Buckets）、猫队（the Cats）、运球者队（the Dribblers）和大象队（the Elephants）。当报纸的体育编辑斯库普·麦吉（Scoop McGee）从当地五金店挑选的几位本地专家那里拿到这些排名时，他沮丧地发现专家们的意见似乎并不完全一致，所以他想知道该发布怎样的一份排名，才能最准确地反映他从专家那里得到的这些排名情况。他发现，在所有可能的排名中找到中位数排名是一种可行的方法。

中位数排名的计算方式如下：给定任意两个排名，例如 ACDBE 和 ABCDE，这两个排名之间的距离定义为两队之间相对顺序不同的总对数。在我们的例子中，球队对 B 和 C 在这两个排名中的顺序不同（第一个排名中 C 在 B 之上，而第二个排名则相反）。这两个排名中意见不一致的另一对球队是 B 和 D；因此，这两个排名之间的距离是 2。一组排名的中位数排名是这样一种排名，它与所有给定排名的距离之和最小（注意，可能存在多个中位数排名）。中位数排名可能是也可能不是给定排名中的某一个。

假设有 4 位投票者给出了以下排名：ABDC E、BACDE、ABCED 和 ACBDE。考虑两个候选中位数排名 ABCDE 和 CDEAB。排名 ABCDE 与这 4 个投票排名的距离之和是 1 + 1 + 1 + 1 = 4。我们将这个和称为排名 ABCDE 的值。排名 CDEAB 的值是 7 + 7 + 7 + 5 = 26。

事实上，ABCDE 就是中位数排名，其值为 4。

输入格式

将有多个输入集。每个输入集的第一行是一个正整数 n，单独占一行，接下来是 n 行（n 不超过 100），每行包含字母 A、B、C、D 和 E 的一种排列，左对齐且没有空格。最后一个输入集之后是一行包含 0 的数据，表示输入结束。

输出格式

每个输入集的输出应该是一行，格式如下：

ranking is the median ranking with value value.

当然，ranking 应该替换为正确的排名，value 应该替换为正确的值。如果存在多个中位数排名，你应该输出按字母顺序排在前面的那个。

输入数据 1

4
ABDCE
BACDE
ABCED
ACBDE
0

输出数据 1

ABCDE is the median ranking with value 4.

题目来源

2004 年美国中东部地区竞赛