청취 기록의 대표 행

문제

한 음악 스트리밍 서비스의 데이터 담당자는 하루 동안 수집한 청취 기록을 정제하고 있다. 이번 작업에 전달된 기록은 모두 같은 날짜에 발생한 것이며, 각 행에는 이용자 번호, 청취 시작 시각, 청취 시간이 정수로 들어 있다. 시작 시각은 그날 0시부터 지난 분의 수이고, 청취 시간의 단위는 초다. 수집 과정에서 기록이 늦게 도착할 수 있으므로 입력 순서와 시작 시각의 순서는 같다고 보장되지 않는다. 이번 집계에서는 청취 시간이 30초 이상 300초 이하인 행만 유효한 기록으로 인정한다. 30초보다 짧거나 300초보다 긴 행은 오류 또는 집계 대상 밖의 기록으로 보고 제거한다. 두 경계인 30초와 300초는 모두 유효하다. 이용자 번호와 시작 시각은 입력 제약을 만족하므로 청취 시간 외의 항목을 검사할 필요는 없다. 유효하지 않은 행을 제거한 뒤, 이용자마다 대표 행을 최대 하나만 남긴다. 같은 이용자의 유효한 행이 여러 개라면 시작 시각이 가장 큰 행을 대표로 선택한다. 시작 시각까지 같은 행이 여러 개라면 원래 입력에서 더 뒤에 나온 행을 선택한다. 입력에서 뒤에 있다는 것은 첫째 줄의 기록 수를 제외하고, 기록이 적힌 줄의 순서가 더 뒤라는 뜻이다. 청취 시간이 더 긴 행을 우선하는 규칙은 없다. 검증은 대표 행 선택보다 먼저 적용한다. 따라서 시작 시각이 늦은 행이라도 유효하지 않으면 그 이용자의 이전 유효 기록을 지우지 않는다. 유효한 행이 하나도 없는 이용자는 결과에 포함하지 않는다. 남긴 대표 행들을 이용자 번호가 작은 순서로 출력하는 프로그램을 작성한다. 먼저 대표 행의 개수를 출력하고, 이어서 각 대표 행의 이용자 번호, 시작 시각, 청취 시간을 출력한다. 전체 기록 중 유효한 행이 하나도 없다면 개수 0만 출력한다.

입력

첫째 줄에 기록 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개의 줄에 정수 U, T, D가 공백으로 구분되어 주어진다. U는 이용자 번호, T는 시작 시각, D는 청취 시간이다. 1 ≤ U ≤ 9,999, 0 ≤ T ≤ 1,439, 0 ≤ D ≤ 600이다.
같은 이용자 번호가 여러 번 등장할 수 있으며, 세 값이 모두 같은 행도 여러 번 등장할 수 있다.

출력

첫째 줄에 남긴 대표 행의 개수 M을 출력한다. 다음 M개의 줄에 대표 행의 이용자 번호, 시작 시각, 청취 시간을 공백으로 구분하여 출력한다. 이용자 번호가 작은 순서로 출력해야 한다. M이 0이면 첫째 줄만 출력한다.

7
12 500 120
3 600 30
12 700 20
3 600 240
12 500 180
8 900 301
8 100 300

3
3 600 240
8 100 300
12 500 180

4
1 0 0
2 1439 600
1 100 29
9 50 301

0

4
5 200 100
5 100 200
2 0 30
5 200 30

2
2 0 30
5 200 30

출처: Devin.KR 자체 제작