시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB22513311358.854%

문제

대전대신고등학교 앞 버스 정류장에는 여러 노선의 버스가 다닌다. 오량인은 $X$시 $Y$분에 버스 정류장에 도착했다. 어서 집에 가고 싶은 오량인은 가장 빨리 탈 수 있는 버스가 언제 오는지 알고 싶어 한다.

각 버스 노선마다 첫차 시각과 배차 간격이 정해져 있다. 각 노선의 버스는 첫차 시각부터 $23$시 $59$분까지 운행하며, 운행 시간 동안 배차 간격만큼 차이를 두고 버스 정류장에서 출발한다. 자정부터 첫차 시각 이전까지는 운행하지 않는다.

버스의 운행은 매일 동일하며, 자정이 넘어가 날짜가 바뀌면 다음 날 첫차 시각부터 같은 규칙으로 운행이 재개된다. 그러므로 오량인은 다음 날 첫차를 기다릴 수도 있다.

오량인을 도와 $X$시 $Y$분 이후에 가장 빨리 도착하는 버스의 도착 시각을 출력해 주는 프로그램을 작성하자!

입력

첫번째 줄에 오량인이 버스 정류장에 도착한 시각을 나타내는 두 정수 $X$와 $Y$가 공백으로 구분되어 주어진다. $(0 \leq X \leq 23;$ $0 \leq Y \leq 59)$

두번째 줄에 버스 노선의 개수 $N$이 주어진다. $(1 \leq N \leq 100)$

세번째 줄부터 $N$개의 줄에 걸쳐 $i+2$번째 줄에 세 정수 $x_i, y_i, d_i$가 주어진다. 이는 $i$번째 노선의 버스는 첫차 시각이 $x_i$시 $y_i$분이고 배차 간격이 $d_i$분임을 의미한다. $(0\le x_i\le 23;$ $0\le y_i\le 59;$ $1\le d_i\le 120;$ $x_i+y_i>0)$

$0$시 $0$분이 첫차 시각인 노선은 없음에 유의하라.

출력

첫번째 줄에 현재 시각 이후에 가장 빨리 도착하는 버스의 도착 시각을 $\operatorname{HH:MM}$ 형태로 출력한다. 필요한 경우 자정을 넘어 다음 날의 첫차 시각도 고려한다.

예제 입력 1

23 59
2
0 1 1
23 58 2

예제 출력 1

23:59

첫번째 노선의 첫차 시각은 $0$시 $1$분이고 배차 간격은 $1$분이므로 매 분마다 첫번째 노선의 버스가 도착한다.

두번째 노선의 첫차 시각은 $23$시 $58$분이고 배차 간격은 $2$분이므로 두번째 노선의 버스는 $23$시 $58$분에만 도착한다.

오량인은 $23$시 $59$분에 도착하는 첫번째 노선의 버스를 탈 수 있다.

예제 입력 2

23 30
2
23 20 80
0 12 60

예제 출력 2

00:12

첫번째 노선의 첫차 시각은 $23$시 $20$분이고 배차 간격은 $80$분이므로 첫번째 노선의 버스는 $23$시 $20$분에만 도착한다.

두번째 노선의 첫차 시각은 $0$시 $12$분이고 배차 간격은 $60$분이므로 두번째 노선의 버스는 매 시 $12$분에 도착한다.

오량인은 다음 날 $0$시 $12$분에 도착하는 두번째 노선의 버스를 탈 수 있다.

예제 입력 3

9 30
3
8 0 15
9 45 10
10 0 30

예제 출력 3

09:30

예제 입력 4

14 20
4
12 0 60
14 0 50
14 15 10
15 0 30

예제 출력 4

14:25