학원 예약 로그의 마지막 상태

문제

한 학원의 운영 서버는 수업 예약 요청이 처리될 때마다 로그를 남긴다. 같은 예약 요청이 다시 처리되거나 수업이 변경되면 동일한 요청 번호로 새 로그가 생긴다. 운영 담당자는 여러 서버에서 모은 로그 파일을 받아, 각 요청의 최종 상태를 기준으로 수업별 정상 예약 수를 집계하려고 한다. 로그 한 줄은 시각, 요청 번호, 수업 번호, 처리 상태를 이 순서로 적고 각 항목 사이에 세로줄 문자 |를 하나씩 넣은 형태이다. 앞의 세 항목은 정수이고, 처리 상태는 OK 또는 FAIL이다. OK는 해당 요청이 그 수업의 정상 예약으로 처리되었다는 뜻이며, FAIL은 해당 요청이 정상 예약으로 인정되지 않는다는 뜻이다. FAIL인 줄에도 수업 번호는 기록되지만 집계에 더하지 않는다. 수집된 로그는 시각순으로 정렬되어 있지 않다. 같은 요청 번호에 속하는 로그 중 시각이 가장 큰 줄을 그 요청의 최종 기록으로 선택한다. 가장 큰 시각이 같은 줄이 여러 개라면 입력에서 더 뒤에 등장한 줄을 선택한다. 요청 번호가 다르면 서로 다른 예약 요청이며, 같은 수업을 가리키더라도 각각 한 건으로 센다. 한 요청의 수업 번호는 로그가 갱신되면서 달라질 수 있다. 이전 기록이 OK였더라도 최종 기록이 FAIL이면 그 요청은 어느 수업에도 더하지 않는다. 최종 기록이 OK라면 오직 그 최종 기록에 적힌 수업에 한 건을 더한다. 따라서 모든 OK 로그를 그대로 세거나, 입력의 마지막 줄만 시각 확인 없이 선택해서는 안 된다. 집계 결과가 한 건 이상인 수업만 출력한다. 정상 예약 수가 많은 수업을 먼저 출력하고, 수가 같으면 수업 번호가 작은 수업을 먼저 출력한다. 정상 예약이 하나도 남지 않았다면 NONE을 출력한다. 입력에 한 번도 나타나지 않은 수업과 정상 예약 수가 0인 수업은 결과 목록에 넣지 않는다.

입력

첫째 줄에 로그 수 N이 정수로 주어진다.
다음 N개 줄에 시각|요청번호|수업번호|상태 형식의 로그가 주어진다. 각 줄에는 공백이 없고, 정수는 불필요한 앞자리 0 없이 십진수로 표기된다. 시각 0은 문자 0으로 표기된다.
1 ≤ N ≤ 15,000
0 ≤ 시각 ≤ 999,999
1 ≤ 요청 번호 ≤ 99,999
1 ≤ 수업 번호 ≤ 999
상태는 OK 또는 FAIL이다.

출력

정상 예약이 남아 있으면 첫째 줄에 정상 예약 수가 1 이상인 수업의 개수 M을 출력한다. 이어서 M개 줄에 수업 번호와 정상 예약 수를 공백으로 구분하여 출력한다. 정상 예약 수의 내림차순으로 출력하며, 수가 같으면 수업 번호의 오름차순으로 출력한다. 정상 예약이 하나도 없으면 다른 내용 없이 NONE 한 줄만 출력한다.

7
12|31|8|OK
4|32|3|OK
18|31|3|OK
9|32|3|FAIL
7|33|8|OK
18|31|5|OK
3|34|5|OK

2
5 2
8 1

4
100|1|2|FAIL
90|1|2|OK
8|2|4|OK
8|2|4|FAIL

NONE

5
0|7|12|OK
5|8|4|OK
2|9|12|OK
10|7|4|OK
1|10|12|OK

2
4 2
12 2

출처: Devin.KR 자체 제작