스마트 홈 상태 복원

문제

스마트 홈의 운영 서버가 여러 장치에서 전송한 상태 로그를 모았다. 백엔드 운영 담당자는 이 로그를 이용해 현재 켜진 것으로 판단되는 장치의 목록을 복원하려고 한다. 각 로그에는 장치 번호, 상태를 측정한 시각, 측정한 상태가 들어 있다. 상태는 정수 0 또는 1로 기록하며, 0은 꺼짐을, 1은 켜짐을 뜻한다. 장치가 보낸 로그는 통신 지연 때문에 측정 시각과 다른 순서로 서버에 도착할 수 있다. 따라서 입력에서 뒤에 나온 로그가 항상 더 새로운 상태를 나타내는 것은 아니다. 각 장치의 현재 상태는 그 장치의 로그 중 측정 시각이 가장 큰 로그의 상태로 정한다. 서로 다른 장치의 측정 시각은 비교할 필요가 없으며, 한 장치의 로그가 다른 장치의 상태에 영향을 주는 일도 없다. 같은 장치에 대해 측정 시각이 같은 로그가 여러 개 있을 수도 있다. 이 경우에는 서버가 나중에 받은 로그를 사용한다. 입력의 로그는 서버가 받은 순서로 주어지므로, 장치 번호와 측정 시각이 모두 같다면 입력에서 더 뒤에 있는 로그가 우선이다. 상태가 같은 로그가 반복되어도 별도의 장치로 세지 않는다. 로그에 한 번도 등장하지 않은 장치의 상태는 알 수 없으므로 결과에 포함하지 않는다. 또한 로그가 있다는 이유만으로 장치를 결과에 포함해서는 안 되며, 위 규칙으로 결정한 현재 상태가 1인 장치만 포함한다. 켜진 장치가 하나도 없을 수도 있다. 운영 담당자가 점검 목록으로 바로 사용할 수 있도록, 켜진 장치의 수를 구하고 해당 장치 번호를 중복 없이 오름차순으로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 로그 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개의 줄에는 로그 하나를 나타내는 정수 D, T, S가 공백으로 구분되어 주어진다. D는 장치 번호, T는 측정 시각, S는 상태이다. 1 ≤ D ≤ 1,000, 0 ≤ T ≤ 999,999, S ∈ {0, 1}이다.
로그는 서버가 받은 순서로 주어지며, 측정 시각 순서로 정렬되어 있다는 보장은 없다.

출력

첫째 줄에 현재 상태가 1인 장치의 수 K를 출력한다. K가 1 이상이면 둘째 줄에 해당 장치 번호 K개를 공백으로 구분하여 오름차순으로 출력한다. K가 0이면 첫째 줄의 0만 출력한다.

7
8 40 1
2 70 0
8 30 0
5 12 1
2 70 1
5 15 0
9 0 1

3
2 8 9

4
1 10 1
1 10 0
4 20 0
4 19 1

0

3
6 2 1
6 2 1
6 1 0

1
6

출처: Devin.KR 자체 제작