선거

지젤은 방금 국회의원 선거에서 투표를 했다. 그녀의 나라에서는 혼합 비례 대표제(MMP)라는 방식으로 국회의원을 선출한다. 기본적으로 의원의 절반은 지역구에서, 나머지 절반은 비례 대표로 정당 명부에서 선출한다. 각 유권자는 지역구 대표자에게 한 표, 정당에게 한 표, 이렇게 두 표를 행사한다.

각 지역구에서는 단일 승자 선거 제도인 소선거구제로 대표자를 선출한다. 이 제도는 매우 단순하다. 가장 많은 표를 얻은 후보가 의석을 차지한다. 지역구의 수는 전체 의석 수의 절반이며, 지리적 구역에 따라 정해진다.

각 정당에는 그 정당에 투표한 표의 비율에 따라 의석이 배정된다. 전체 정당 투표의 5퍼센트 이상을 얻거나 지역구 의석을 3석 이상 얻은 정당만 의석을 배정받을 자격이 있고, 두 조건 모두 충족하지 못한 정당은 다음 절차에서 제외된다. 자격을 갖춘 각 정당의 의석 수는 다음 값으로 결정된다.

(전체 의석 수) × ((그 정당에 투표한 표 수) / (자격을 갖춘 모든 정당에 투표한 표의 총수)).

위 식의 곱셈 인자는 전체 의석 수이며, 비례 대표 의석 수(즉 의원의 절반)가 아니다. 각 정당은 이 값의 정수 부분에 해당하는 의석을 받는다. 보통 남는 의석이 생기며, 이 의석은 소수 부분이 큰 순서대로 정당에 배정되고, 각 정당은 최대 한 석을 더 받는다. 소수 부분이 같은 정당이 둘 이상이면 더 많은 표를 얻은 정당이 우선한다.

위 절차로 배정된 의석 수는 지역구 의석과 비례 대표 의석을 모두 포함한다. 따라서 각 정당은 배정된 의석 수에서 지역구 의석 수를 뺀 만큼 명부에서 의원을 추가할 수 있다. 이 의원은 정당이 미리 정한 순서대로 선택한다. 정당 명부에 있는 후보 중 이미 지역구 대표 의석을 가진 후보가 있으면(각 지역구 후보는 명부에도 오를 수 있으므로 이런 일이 생긴다) 그 후보는 세지 않고 다음 후보를 추가한다.

지역구에서 당선된 후보는 절대 의석을 잃지 않는다. 정당이 지역구에서 이긴 수가 그 정당의 정당 투표로 배정된 의석 수를 넘는 경우도 있다. 이때는 지역구 당선자 전원이 국회 의석을 받으며, 정당 명부에서 더 선출되는 의원은 없다. 의석 배정 자격이 없는 정당의 후보에게도 같은 원칙이 적용된다. 이로 인해 전체 의석 수가 늘어난다. 이렇게 추가된 의석을 초과 의석이라고 한다.

예를 들어 보자. 세 정당 A, B, C가 8석을 두고 경쟁하는데, 정당 A가 지역구 1석과 정당 투표 9,000표, 정당 B가 1석과 8,000표, 정당 C가 2석과 3,000표를 얻었다고 하자. 전체 정당 투표 수는 9000 + 8000 + 3000 = 20000이므로 5퍼센트 기준은 20000 × (5/100) = 1000이다. 이 기준에 따라 모든 정당이 의석을 배정받을 자격이 있다. 식에 따라 (8 × 9000)/20000 = 3.6, (8 × 8000)/20000 = 3.2, (8 × 3000)/20000 = 1.2이므로 정당 A, B, C는 각각 3석, 3석, 1석을 받는다. 남는 의석이 하나 있고, 소수 부분이 가장 큰 0.6(= 3.6 − 3)을 가진 정당 A가 가져간다. 결국 정당 A는 모두 4석을 얻고, 지역구 1석을 얻었으므로 정당 A 명부에서 3명을 더 선택한다. 마찬가지로 정당 B 명부에서 2명을 더 선택한다. 반면 정당 C는 지역구에서 2석을 이겼지만 의석은 1석만 받는다. 따라서 정당 C 명부에서는 아무도 선택되지 않고 초과 의석이 하나 생긴다. 그러므로 전체 당선자 수는 9명이 된다. 이 예는 예제 입력과 출력의 첫 번째 데이터 세트에 해당한다.

여러분은 어느 후보가 의석을 차지하는지 결정하는 프로그램을 작성해야 한다.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N M
Party1
Party2
...
PartyM
Constituency1
Constituency2
...
ConstituencyN/2

N은 의석 수를 나타내는 양의 짝수 정수이다. M은 정당 수를 나타내는 양의 정수이다. Partyi는 i번째 정당의 설명이다. Constituencyi는 i번째 지역구의 설명이다.

각 정당 설명의 형식은 다음과 같다.

PartyName C V
Name1
Name2
...
NameC

PartyName은 정당 이름이다. C는 정당 명부에 있는 후보 수를 나타내는 양의 정수이다. V는 그 정당에 투표한 표 수를 나타내는 음이 아닌 정수이다. Namei는 정당 명부에서 i번째로 우선순위가 높은 후보의 이름이다.

각 지역구 설명의 형식은 다음과 같다.

C
Name1 Party1 V1
Name2 Party2 V2
...
NameC PartyC VC

C는 지역구 후보 수를 나타내는 2 이상의 양의 정수이다. Namei는 지역구에서 i번째 후보의 이름이다. Partyi는 i번째 후보가 속한 정당의 이름이다. Vi는 i번째 후보에 투표한 표 수를 나타내는 음이 아닌 정수이다.

입력은 두 개의 0이 있는 줄로 끝난다. 이 줄은 처리하지 않는다.

다음 사항을 가정할 수 있다.

• 각 정당의 이름은 대문자로 시작하고 대문자와 숫자로만 이루어진, 길이 10 이하의 문자열이다. 각 후보의 이름은 소문자로 시작하고 소문자와 숫자로만 이루어진, 길이 20 이하의 문자열이다. 이름이 같은 정당이나 후보는 없다.
• 정당 수, 의석 수, 서로 다른 후보의 총수는 각각 20, 200, 1,000을 넘지 않는다. 전체 정당 투표 수와 각 지역구의 전체 투표 수도 10,000,000을 넘지 않는다.
• 같은 정당 투표 수를 얻는 정당은 둘 이상 없다. 또한 각 지역구에서 같은 지역구 투표 수를 얻는 후보는 둘 이상 없다.
• 각 정당 명부에는 후보가 충분히 있다. 즉 정당은 항상 명부에서 필요한 수만큼 후보를 선택할 수 있다.
• 모든 후보는 정확히 하나의 정당에 속한다. 어떤 후보도 둘 이상의 지역구에 출마할 수 없다. 하지만 각 후보는 데이터 세트에 최대 두 번, 정당 명부에 한 번과 지역구 설명에 한 번 나타날 수 있다.
• 입력의 데이터 세트 수는 50을 넘지 않는다.

각 데이터 세트마다 당선된 모든 사람의 이름을 ASCII 코드에 따른 사전 순으로 한 줄에 하나씩 출력한다. 연속한 두 데이터 세트 사이에는 빈 줄을 출력한다.