지하철 임시 승강장 안내

문제

한 지하철역은 공사 기간에 여러 임시 승강장 중 하나를 골라 승객에게 안내한다. 안내 프로그램에는 승객이 이동을 시작하는 시각 T와 이용하려는 방향 D가 주어진다. 각 승강장에는 이동에 필요한 시간 W, 열차 출발 시각 E, 열차의 방향 R이 등록되어 있다. 모든 시각은 같은 날의 기준 시점부터 지난 분을 나타내며, 날짜가 바뀌는 경우는 없다. 승객이 어떤 승강장에 도착하는 시각은 T에 그 승강장의 이동 시간 W를 더한 값이다. 해당 승강장의 열차 방향 R이 승객의 방향 D와 같고, 도착 시각이 열차 출발 시각 E 이하일 때만 그 승강장을 이용할 수 있다. 도착한 순간 열차가 출발하는 경우에도 탑승할 수 있다고 정한다. 방향이 다르거나 열차가 먼저 출발하는 승강장은 안내 후보에서 제외한다. 이용할 수 있는 승강장이 여러 개이면 열차 출발 시각 E가 가장 이른 승강장을 선택한다. 출발 시각이 같은 후보가 여러 개이면 이동 시간 W가 가장 짧은 승강장을 선택한다. 출발 시각과 이동 시간이 모두 같은 후보가 여러 개이면 승강장 번호가 가장 작은 곳을 선택한다. 승강장 번호는 입력된 순서대로 1번부터 N번까지 부여된다. 안내의 기준은 승강장에 도착한 뒤 기다리는 시간의 길이가 아니다. 먼저 출발 시각을 비교하고, 그 값이 같을 때만 이동 시간을 비교해야 한다. 승객은 하나의 승강장으로 바로 이동하며 다른 승강장으로 옮겨 타는 경로는 고려하지 않는다. 조건을 만족하는 승강장이 하나도 없으면 안내할 곳이 없다는 뜻으로 0을 출력한다. 그 외에는 규칙에 따라 선택한 승강장 번호 하나를 출력한다.

입력

첫째 줄에 정수 N, T, D가 주어진다.
다음 N개 줄 중 i번째 줄에 i번 승강장의 정수 W, E, R이 주어진다.
1 ≤ N ≤ 1,000
0 ≤ T ≤ 1,000
1 ≤ W ≤ 1,000
0 ≤ E ≤ 2,000
D와 R은 각각 0 또는 1이다.

출력

선택한 승강장 번호를 첫째 줄에 출력한다. 이용 가능한 승강장이 없으면 0을 출력한다.

5 20 1
5 30 1
3 30 1
3 30 1
1 29 0
11 30 1

2

3 10 0
4 14 0
1 15 0
2 12 1

1

2 10 1
2 11 1
1 20 0

0

출처: Devin.KR 자체 제작