시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 24 12 12 52.174%

문제

입력 제한 외 난이도에 따른 문제의 차이는 없다.

코로나 시국에도 꺾이지 않은 여러분들의 학구열에 힘입어, 2020년 올해도 어김없이 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)가 열렸다!

올해 ANSI 회장이자 대회의 운영을 맡은 세훈에게는 한가지 고민이 있다. APC 에는 대회 종료 1시간 전부터 참가자들의 제출을 스코어보드에 반영하지 않는 프리징이라는 룰이 있고, 대회가 끝난 뒤 참가자들과 함께 스코어보드에 결과를 하나씩 반영하며 결과에 대한 기대와 분위기를 끌어올리는 언프리징시간이 준비되어있다. 하지만 코로나로 인해 대회가 온라인으로 진행되면서, 세훈이는 언프리징 시간이 참가자들에게 다소 무료하게 다가오진 않을까 걱정이 되었다. 고심 끝에 세훈이는 특별상 역전의 제왕을 기획했다! 세훈이는 역전의 제왕을 프리징을 녹이는 동안 가장 극적인 상황을 연출한 참가자에게 주고자 한다. 이를 평가하기 위해 '역전 포인트'를 계산하는데, 역전포인트를 이해하기 위해서는 몇가지 규칙을 자세히 알아둘 필요가 있다.

올해 APC의 순위는 아래 조건을 순서대로 적용했을 때, 상위에 있는 조건을 먼저 만족한 참가자가 더 높은 순위를 가진다.

  1. 해결한 문제의 수가 더 많은 참가자

  2. 패널티의 총합이 더 적은 참가자

  3. 마지막 정답 제출 시간이 빠른 참가자

여기서 페널티는 문제마다 독립적으로 계산되며, 각 문제의 패널티는 [처음 맞았습니다!! 를 받은 시간] + [해당 문제의 제출 횟수 - 1] x 20 공식에 따라 분단위로 계산된다. 맞았습니다!!를 받기 전에는 패널티의 총합에 가산되지 않는다.

모든 참가자는 스코어보드를 통해 실시간으로 다른 참가자들의 등수와 제출한 문제 등을 확인할 수 있으며, 이는 참가자들이 문제를 푸는 순서를 결정하는 데 전략적으로 큰 도움이 될 수 있다.

스코어보드는 대회 종료 1시간 전부터 참가자들의 제출을 반영하지 않는 프리징 상태가 되며, 대회가 끝난 뒤 언프리징 시간에 프리징 상태동안 제출된 코드들의 결과를 아래의 규칙에 따라 하나씩 공개해 최종 순위를 결정한다.

  1. 프리징 이전의 제출은 이미 스코어보드에 반영 되었으므로 프리징 이후 정답을 맞춘 문제들만 순위변동에 영향을 준다.

  2. 프리징 상태에서 가장 마지막 순위 참가자의 제출부터 공개한다.

  3. 프리징 이후 한 참가자가 제출한 문제가 여러개일 경우 문제의 번호가 가장 빠른 제출부터 공개된다.

  4. 3번에 의해 순위에 변동이 생길 경우 즉시 스코어보드에 반영되어 순위가 변경 되며, 다시 가장 마지막 순위 참가자의 제출이 공개된다.

  5. 가장 마지막 순위 참가자의 제출이 모두 공개되면 그 순위가 확정되며, 확정되지 않은 가장 마지막 순위 참가자의 제출이 공개된다.

  6. 모든 참가자의 제출이 모두 공개되면 스코어보드 및 최종순위가 결정된다.

역전 포인트는 다음과 같이 계산된다.

  1. 프리징을 녹이는 중 순위가 오르는 참가자는 올라간 순위만큼 역전 포인트를 얻는다.

  2. 다른 참가자에 의해 순위가 하락해도 역전 포인트는 변하지 않는다.

  3. 역전 포인트를 가장 많이 쌓은 참가자에게 역전의 제왕이 수여된다.

  4. 역전 포인트가 동일한 참가자가 존재할 경우 가장 순위가 높은 참가자에게 역전의 제왕이 수여된다.

세훈이는 역전의 제왕을 받게될 참가자를 자동으로 구하는 프로그램을 당신에게 의뢰했다.

세훈이를 위해 대회 중 제출된 제출이력을 입력하면 역전의 제왕을 알려주는 프로그램을 작성해주자!

채점 서버의 건강을 위해 각 참가자가 대회 중 가능한 제출 횟수는 100회로 제한되며, 모든 참가자들은 프리징 이전에 한문제 이상 맞았다고 가정한다.

입력

첫번째 줄에는 참가자들의 수 N (1 ≤ N ≤ 50), 대회 중 제출된 참가자들의 제출이력의 수 M (NM ≤ 13×N)이 주어진다.

두번째 줄부터 M 줄에 걸쳐 참가자들의 제출이력이 주어진다. 제출이력은 문제의 단순화를 위해 맞았습니다!!를 받은 제출만을 입력받는다.

제출이력은 제출시간, 참가자 번호 id (1 ≤ idN), 문제번호 p (1 ≤ p ≤ 13), 제출횟수 s (1 ≤ s ≤ 100) 순으로 주어진다. 각 참가자의 제출 횟수는 총 100회를 넘지 않는다. 제출시간은 hh:mm 형식으로 주어지며, 스코어보드는 03:00를 지난 후 부터 프리징 된다. (00:00 < hh:mm ≤ 04:00)

제출이력은 제출한 시간 순서대로 주어지며, 두 제출이 같은 시, 분에 제출 되더라도 먼저 등장한 이력이 더 빠른 제출이다.

단,  같은 참가자가 동일한 문제를 여러번 맞추는 경우는 존재하지 않는다.

출력

역전포인트를 가장 많이 쌓아 역전의 제왕을 수상한 참가자 번호를 출력한다.

제한

1 ≤ N ≤ 50

대회도중 혹은 언프리징 과정 중 정답을 맞은 문제수와 패널티까지 같은 참가자 존재하는 상황이 발생하지 않는다. 즉 APC 순위 규칙 3번을 고려하는 상황은 없다.

예제 입력 1

3 7
00:38 1 4 3
01:16 2 2 1
02:01 3 1 2
03:00 1 2 3
03:04 2 3 2
03:18 2 1 1
03:54 1 3 6

예제 출력 1

2

다음은 예제1에서 주어지는 입력을 표로 나타낸 것이다. 보다 쉬운 이해를 위해 참가자의 이름을 임의로 부여하였고, 실제 예제에서는 주어지지 않는다.

<그림 1> 예제 1번

또한 다음 그림은 예제 1번을 언프리징 시간에 결과가 스코어보드에 반영되어 역전 포인트를 쌓는 과정을 나타낸 것이다.

<그림2> 역전포인트가 쌓이는 과정

위 2번의 과정에서 Lee와 Mike는 역전포인트를 1점씩 획득하였고, 마지막으로 Lee의 3번문제 제출이력이 반영되면 Lee가 1위가 되어 역전포인트 1점을 추가하며 역전포인트 2점으로 역전의 제왕에 선정된다.