월드컵 조 추첨

2018 FIFA 월드컵 본선 조 추첨은 12월 1일 금요일 모스크바의 크렘린 궁전에서 열렸다. FIFA는 몇 달 전 공식 웹사이트에 추첨 방식을 공개했고, 내용은 다음과 같다.

본선에 오른 32개 팀을 2017년 10월 FIFA 랭킹에 따라 네 개의 포트로 나눈다. 포트 1에는 개최국 Russia와 랭킹이 가장 높은 일곱 팀이 들어가고, 그다음 여덟 팀이 포트 2에 들어가며, 같은 방식으로 포트 3과 포트 4를 채운다. 그런 다음 A부터 H까지 이름이 붙은 여덟 개 조에 네 팀씩 배정한다. 포트는 1번부터 4번까지 순서대로 비운다. 추첨 결과는 다음 두 규칙을 지켜야 한다.

1. 같은 포트에 속한 두 팀은 같은 조에 들어갈 수 없다.
2. UEFA를 뺀 나머지 대륙연맹은 같은 연맹 소속 두 팀이 같은 조에 들어갈 수 없다. UEFA는 본선 진출 팀이 14개로 조의 수인 8보다 많아 예외이고, 한 조에 최대 두 팀까지 들어갈 수 있다.

조는 A가 가장 왼쪽, H가 가장 오른쪽이 되도록 알파벳 순으로 늘어놓는다. 추첨의 각 단계에서 포트 $i$의 팀 $x$가 뽑히면, 조 A부터 왼쪽에서 오른쪽으로 살펴보며 다음 두 조건을 함께 만족하는 첫 번째 조에 $x$를 넣는다. 첫째, $x$를 그 조에 넣어도 규칙 1과 규칙 2를 어기지 않는다. 둘째, 포트 $i$에서 아직 뽑히지 않은 나머지 팀을 이후 단계에 규칙 1과 규칙 2를 어기지 않으면서 모두 배정하는 방법이 남아 있다. 포트 1부터 포트 $i-1$까지의 팀이 어떻게 배정되어 있든 포트 $i$의 여덟 팀을 규칙 1과 규칙 2에 맞게 배정하는 방법은 언제나 존재한다고 전산학자들이 FIFA에 확인해 주었다.

아래 표는 네 포트의 구성이다. 표에서 $x$ $(r, c)$는 팀 $x$가 대륙연맹 $c$ 소속이고 FIFA 랭킹이 $r$위라는 뜻이다. 포트별 추첨 순서가 주어지면 추첨을 그대로 시뮬레이션해 각 조의 결과를 보고하는 프로그램을 작성하라.

입력에는 여러 개의 테스트 케이스가 들어 있다. 각 테스트 케이스는 네 줄이다. $i$번째 줄에는 포트 $i$에 속한 여덟 팀의 이름이 추첨 순서대로, 즉 왼쪽에서 오른쪽으로 주어진다. 팀 이름은 표에 적힌 그대로 쓰고 쉼표로 구분하며, 이름 앞이나 뒤에 공백이 있을 수 있다. 개최국을 A조에 넣는 오랜 관례에 따라 모든 테스트 케이스에서 포트 1의 첫 번째 팀은 Russia이다. 입력은 "End"로 끝나고, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 주어진 추첨 순서로 추첨을 시뮬레이션한 다음, 각 조에 속한 네 팀의 랭킹을 모두 더해 그 조의 가중치를 구한다. 조마다 조 이름(대문자 한 글자)과 가중치를 공백 하나로 구분해 한 줄에 출력한다. 출력 순서는 가중치의 오름차순, 즉 가중치가 가장 작은 가장 강한 조부터 가중치가 가장 큰 가장 약한 조까지다. 가중치가 같은 조끼리는 조 이름의 알파벳 순으로 출력한다.