늦게 출발하는 할인 항공권

문제

항공권 안내 화면에 같은 공항에서 같은 날 출발하는 여러 항공편이 등록되어 있다. 각 항공편에는 도착지 번호, 출발 시각, 항공권 가격이 하나씩 정해져 있다. 출발 시각은 그날 0시부터 지난 분으로 나타낸다. 항공편은 출발 시각과 관계없는 순서로 등록되며, 입력 순서대로 1번부터 N번까지 번호가 붙는다. 안내 화면은 출발을 늦추는 대신 더 저렴하게 이동할 수 있는 항공편에 할인 표시를 붙이려고 한다. 항공편 하나를 검사할 때 비교 대상은 도착지가 같고 출발 시각이 엄격히 이른 모든 항공편이다. 비교 대상이 하나 이상 있으며, 검사하는 항공편의 가격이 그 비교 대상들의 모든 가격보다 엄격히 작을 때만 할인 표시를 붙인다. 같은 시각에 출발하는 항공편끼리는 서로 비교하지 않는다. 도착지와 출발 시각이 모두 같은 항공편이 여러 개 있어도 각각 별개의 항공편으로 검사한다. 비교 대상에 같은 가격의 항공편이 하나라도 있으면 모든 가격보다 엄격히 작다는 조건을 만족하지 못한다. 같은 도착지에서 가장 이른 시각에 출발하는 항공편들은 비교 대상이 없으므로 가격과 관계없이 할인 표시를 받지 않는다. 비교 대상에는 할인 표시를 받은 항공편과 받지 않은 항공편이 모두 포함된다. 표시를 붙였다고 해서 그 항공편을 목록에서 지우거나 가격을 바꾸지는 않는다. 다른 도착지의 가격은 검사에 영향을 주지 않으며, 더 늦게 출발하는 항공편도 현재 검사하는 항공편의 비교 대상이 아니다. 등록 순서대로 앞에 등장한 항공편만 살펴보면 실제로 더 이른 항공편을 놓칠 수 있다. 반대로 같은 시각의 항공편을 먼저 검사했다는 이유로 비교 대상에 포함해서도 안 된다. 전체 항공편 정보를 이용하여 위 규칙을 만족하는 항공편을 모두 찾는다. 할인 표시를 받는 항공편의 개수와 번호를 출력하되, 번호는 입력 순서에 따른 오름차순으로 출력한다.

입력

첫째 줄에 항공편 수 N이 주어진다. 다음 N개 줄에 i번 항공편의 도착지 번호 D_i, 출발 시각 T_i, 가격 P_i가 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1≤N≤20,000, 1≤D_i≤999, 0≤T_i≤1,439, 1≤P_i≤9,999이다. 도착지, 출발 시각, 가격이 모두 같은 항공편도 여러 개 주어질 수 있다.

출력

첫째 줄에 할인 표시를 받는 항공편의 개수를 출력한다. 둘째 줄에 해당 항공편의 번호를 오름차순으로 공백으로 구분하여 출력한다. 해당 항공편이 없으면 첫째 줄에 0, 둘째 줄에 -1을 출력한다.

6
1 600 70
1 480 90
1 600 60
1 720 65
2 500 40
2 700 40

2
1 3

4
3 100 50
3 100 20
3 200 20
8 0 1

0
-1

5
2 900 10
2 300 40
2 600 30
1 200 80
1 100 90

3
1 3 4

출처: Devin.KR 자체 제작