스마트 홈의 마지막 상태 보고

문제

스마트 홈 운영 서버는 집 안의 여러 기기가 보낸 상태 보고를 모아 저장한다. 보고 한 건에는 보고가 생성된 시각, 기기 번호, 전원 상태가 들어 있다. 전원 상태는 ON 또는 OFF다. 각 보고는 해당 시각에 기기가 직접 확인한 전원 상태를 나타낸다. ON과 OFF는 상태를 뒤집으라는 명령이 아니므로 같은 상태가 여러 번 보고될 수도 있다. 기기마다 통신에 걸리는 시간이 달라서 서버에 저장된 줄의 순서는 보고가 생성된 시각의 순서와 다를 수 있다. 운영 담당자는 저장된 자료를 이용하여 각 기기의 마지막 보고 상태를 정리하려고 한다. 여기서 마지막 보고 상태란 그 기기가 보낸 보고 중 생성 시각이 가장 큰 보고의 상태다. 입력에서 나중에 등장했다는 이유만으로 생성 시각이 더 작은 보고를 선택해서는 안 된다. 같은 기기가 같은 생성 시각으로 여러 보고를 보낸 경우도 있다. 이런 경우 서버는 입력에서 더 뒤에 등장한 보고를 최종 보고로 인정한다. 따라서 한 기기에 대해 생성 시각이 가장 큰 보고가 여러 개라면, 그 보고들 중 입력 줄의 위치가 가장 뒤인 것을 선택한다. 서로 다른 기기의 보고는 선택 과정에 영향을 주지 않는다. 마지막 보고 상태가 ON인 기기들을 찾아 운영 화면에 표시해야 한다. 화면에는 해당 기기의 번호를 작은 것부터 나열하며, 같은 기기 번호는 한 번만 표시한다. 마지막 보고가 OFF인 기기는 이전에 ON을 보고한 적이 있더라도 표시하지 않는다. 자료에 한 번도 등장하지 않은 기기는 이번 작업의 대상이 아니다. 보고는 한 줄에 하나씩 저장되며, 세 항목은 세로줄 문자로 구분되어 있다. 주어진 보고를 모두 처리하여 마지막 보고 상태가 ON인 기기의 수와 번호 목록을 구해야 한다. 해당하는 기기가 하나도 없다면 기기의 수만 0으로 출력하고 번호 목록은 출력하지 않는다.

입력

첫째 줄에 보고의 개수 N이 주어진다.
다음 N개 줄에 보고가 T|D|STATE 형식으로 주어진다. T는 생성 시각, D는 기기 번호, STATE는 ON 또는 OFF다. 각 보고 줄에는 공백이 없다.
N, T, D는 정수이며 1 ≤ N ≤ 20,000, 0 ≤ T ≤ 999,999, 1 ≤ D ≤ 999다. T와 D는 값이 0인 경우를 제외하면 맨 앞에 0이 없는 십진수로 주어진다.
보고는 생성 시각 순서로 주어진다는 보장이 없다. 같은 기기 번호와 생성 시각을 가진 보고가 여러 번 등장할 수 있다.

출력

첫째 줄에 마지막 보고 상태가 ON인 기기의 수 K를 출력한다. K가 1 이상이면 둘째 줄에 해당 기기 번호 K개를 오름차순으로 공백으로 구분하여 출력한다. K가 0이면 첫째 줄에 0만 출력한다.

7
120|8|ON
90|3|ON
100|8|OFF
130|3|OFF
125|21|OFF
125|21|ON
110|5|ON

3
5 8 21

4
8|2|ON
9|2|OFF
6|7|OFF
5|7|ON

0

5
30|10|OFF
30|10|ON
29|10|OFF
30|10|OFF
0|1|ON

1
1

출처: Devin.KR 자체 제작