역전의 제왕 (Normal)

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

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

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

올해 APC의 순위는 아래 조건을 순서대로 적용해 정한다. 앞선 조건을 먼저 만족한 참가자가 더 높은 순위를 가진다.

1. 해결한 문제의 수가 더 많은 참가자
2. 패널티의 총합이 더 적은 참가자
3. 마지막 정답 제출 시간이 빠른 참가자

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

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

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

1. 프리징 이전의 제출은 이미 스코어보드에 반영되었으므로, 프리징 이후 정답을 맞힌 문제만 순위 변동에 영향을 준다.
2. 프리징 상태에서 최하위 참가자의 제출부터 공개한다.
3. 한 참가자가 프리징 이후 여러 문제를 제출했다면, 문제 번호가 가장 빠른 제출부터 공개한다.
4. 3번에 의해 순위에 변동이 생기면 즉시 스코어보드에 반영해 순위를 바꾸고, 다시 최하위 참가자의 제출을 공개한다.
5. 최하위 참가자의 제출을 모두 공개하면 그 순위가 확정된다. 이어서 아직 확정되지 않은 최하위 참가자의 제출을 공개한다.
6. 모든 참가자의 제출을 공개하면 스코어보드와 최종 순위가 결정된다.

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

1. 프리징을 녹이는 중 순위가 오르는 참가자는 올라간 순위만큼 역전 포인트를 얻는다.
2. 다른 참가자에 의해 순위가 내려가도 역전 포인트는 변하지 않는다.
3. 역전 포인트를 가장 많이 쌓은 참가자에게 역전의 제왕이 수여된다.
4. 역전 포인트가 같은 참가자가 있으면 순위가 더 높은 참가자에게 역전의 제왕이 수여된다.

세훈이는 역전의 제왕을 받을 참가자를 자동으로 구하는 프로그램을 당신에게 의뢰했다. 대회 중 제출된 제출 이력을 입력받아 역전의 제왕을 알려주는 프로그램을 작성해 보자.

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

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

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

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

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

같은 참가자가 같은 문제를 여러 번 맞히는 경우는 없다. 각 참가자의 제출 횟수는 총 100회를 넘지 않는다.

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

역전의 제왕(Normal)과 역전의 제왕(Hard)의 차이는 N의 크기뿐이다.

1 ≤ N ≤ 50