알람 시계

휴대폰에서 알람 시간을 설정할 때는 시와 분을 나타내는 네 자리 숫자를 누른다. 예를 들어 12:30으로 설정하려면 1, 2, 3, 0을 차례로 누르면 되고, 9시 30분처럼 시가 한 자리이면 앞에 0을 붙여 0, 9, 3, 0을 누르면 된다.

그런데 꿍은 알람 시간을 잘못 입력하더라도 화면에 표시되는 시는 입력한 시를 24로 나눈 나머지이고, 표시되는 분은 입력한 분을 60으로 나눈 나머지라는 사실을 알게 되었다. 예를 들어 66:79를 입력하면 화면에는 18:19가 표시된다.

꿍은 원하는 알람 시각을 가능한 한 적은 노력으로 맞추고 싶다. 원하는 시각이 화면에 표시되도록 네 자리 숫자를 입력하는 방법 중 총 노력이 가장 작은 입력 시각을 구하라.

키보드는 위 그림과 같다. 키 a에서 키 b로 이동하는 데 필요한 노력은 다음과 같다.

effort(a, b) = |x_a - x_b| + |y_a - y_b|

여기서 (x_a, y_a)와 (x_b, y_b)는 각각 키 a와 키 b의 좌표이다.

전체 노력은 첫 번째 키에서 두 번째 키, 두 번째 키에서 세 번째 키, 세 번째 키에서 네 번째 키로 이동하는 데 필요한 노력의 합이다.

예를 들어 22:45를 입력하는 데 필요한 총 노력은 effort(2, 2) + effort(2, 4) + effort(4, 5) = 0 + 2 + 1 = 3이다.

총 노력이 최소인 입력 시각이 여러 개라면, 그중 가장 이른 입력 시각을 출력하라.

첫 줄에 설정하고 싶은 표시 시각이 HH:MM 형식으로 주어진다. 시 또는 분이 한 자리 수여도 앞에 0이 붙는다.

설정하고 싶은 표시 시각은 00:00 이상 23:59 이하이다.

첫 줄에 답을 HH:MM 형식으로 출력한다. 시 또는 분이 한 자리 수이면 앞에 0을 붙인다.