ICPC 순위표

ICPC 지역 대회의 결과는 대회가 끝난 뒤의 최종 팀 순위로 결정된다. 지역 대회는 여러 팀이 풀어야 하는 여러 문제로 이루어진다.

팀은 푼 문제 수가 많은 순서로 순위가 매겨진다. 푼 문제 수가 같은 팀은 총 시간이 적은 순서로 순위가 매겨진다. 총 시간은 푼 각 문제의 소요 시간을 더한 값이다. 푼 문제의 소요 시간은 대회 시작부터 처음으로 정답 판정을 받은 제출까지 걸린 시간에, 그 문제에서 그 이전에 오답 판정을 받은 제출마다 20분의 페널티를 더한 값이다. 풀지 못한 문제에는 소요 시간이 없다. 동점일 경우, 마지막으로 정답을 받은 풀이의 소요 시간이 더 작은 팀이 더 높은 순위를 차지한다. 이 과정은 필요한 만큼 반복한다(끝에서 두 번째로 정답을 받은 문제, 끝에서 세 번째로 정답을 받은 문제 등). 모든 동점 판정 기준을 다 써도 동점이면 그 팀들은 같은 순위로 매겨지고 팀 번호 순서로 표시된다. 예를 들어 대회에 3팀이 있고 1번 팀과 3번 팀이 모두 1위라면, 2번 팀은 3위가 된다(이 경우 2위는 없다).

이 문제에서는 주어진 입력을 바탕으로 대회의 최종 순위표를 출력하는 프로그램을 작성한다.

입력의 첫 줄에는 대회 매개변수를 정의하는 네 정수 NT NP NS NR가 공백으로 구분되어 주어진다. 각각 팀 수, 문제 수, 제출 수, 표시할 최고 순위 수이다. (2 ≤ NT ≤ 100), (1 ≤ NP ≤ 20), (1 ≤ NS ≤ 10000), (1 ≤ NR ≤ NT). 실제로 표시되는 최고 순위 팀이 NR보다 적을 수도 있다.

다음 NS개 줄에는 제출을 설명하는 네 정수 T P t D가 공백으로 구분되어 주어진다. 각 제출 줄은 팀 번호, 문제 번호, 제출 시각, 판정을 나타낸다. 제출 시각은 대회 시작 이후 지난 분 수이다. (1 ≤ T ≤ NT), (1 ≤ P ≤ NP), (0 ≤ t < 300), D는 제출이 오답이면 0, 정답이면 1이다. t의 값은 이전 줄의 t 값보다 작지 않다. t ≥ 300인 제출은 무시한다.

출력은 대회의 순위표를 가장 좋은 순위부터 가장 나쁜 순위까지 나타내며, 순위 1부터 NR까지의 모든 팀을 보여준다. 각 줄은 네 개의 열로 나뉜 16개 문자로 이루어진다. 첫 번째 열은 순위를 네 문자 필드에 왼쪽 정렬한 것이다. 두 번째 열은 팀 번호를 네 문자 필드에 왼쪽 정렬한 것이다. 세 번째 열은 푼 문제 수를 세 문자 필드에 오른쪽 정렬한 것이다. 네 번째 열은 총 시간을 다섯 문자 필드에 오른쪽 정렬한 것이다.