팀 순위

프리시즌을 맞아 한 지역 신문이 지역 아마추어 농구 리그의 프리시즌 팀 순위를 발표하려고 한다. 팀은 Ants, Buckets, Cats, Dribblers, Elephants 다섯 팀이며, 각각 알파벳 A, B, C, D, E로 나타낸다. 신문의 스포츠 편집자는 여러 지역 전문가에게서 순위를 받았지만, 전문가들의 의견이 완전히 일치하지는 않았다. 그래서 그는 모든 전문가의 순위를 가장 잘 반영하는 하나의 순위를 발표하고자 하며, 그 방법으로 중앙값 순위(median ranking)를 사용하기로 했다.

중앙값 순위는 다음과 같이 정의한다. 두 순위, 예를 들어 ACDBE와 ABCDE가 주어졌을 때, 두 순위 사이의 거리(distance)는 두 순위가 서로 다르게 정렬한 팀 쌍의 개수이다. 이 예에서 쌍 (B, C)는 서로 다르게 정렬되어 있고(첫 번째 순위는 C를 B보다 위에, 두 번째 순위는 그 반대로 둔다), 쌍 (B, D)도 마찬가지이다. 나머지 모든 쌍은 같은 순서이므로, ACDBE와 ABCDE 사이의 거리는 $2$이다.

여러 개의 순위가 주어졌을 때, 어떤 후보 순위의 값(value)은 그 후보 순위로부터 주어진 모든 순위까지의 거리의 합이다. 중앙값 순위는 값이 최소가 되는 순위이다. 중앙값 순위는 여러 개일 수 있으며, 주어진 순위 중 하나일 필요는 없다.

예를 들어 네 명의 전문가가 각각 ABDCE, BACDE, ABCED, ACBDE를 제출했다고 하자. 후보 ABCDE의 값은 $1 + 1 + 1 + 1 = 4$이고, 후보 CDEAB의 값은 $7 + 7 + 7 + 5 = 26$이다. 실제로 ABCDE가 값 $4$를 갖는 중앙값 순위이다.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 한 줄에 양의 정수 $n$ ($n \le 100$)이 주어지고, 이어서 $n$개의 줄이 주어진다. 각 줄에는 알파벳 A, B, C, D, E를 한 번씩 사용한 순열이 공백 없이 주어진다. 입력의 끝은 $0$ 하나만 있는 줄로 표시하며, 이 줄은 데이터 집합의 시작이 아니다.

각 데이터 집합마다 다음 형식으로 한 줄을 출력한다.

<ranking> is the median ranking with value <value>.

여기서 <ranking>은 중앙값 순위이고 <value>는 그 값이다. 중앙값 순위가 여러 개이면 알파벳 순으로 가장 앞서는 것을 출력한다.