시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 37 11 11 40.741%

문제

우리가 핸드폰으로 알람시계를 설정할 때는 시간과 분을 나타내는 4개의 숫자를 입력하기 위해 키보드를 사용한다. 예를 들어, 우리가 12:30으로 알람을 설정하려고 한다면 1,2,3,0을 입력하면 되고 9시30분 같은 경우는 맨 앞에 0을 붙여 0,9,3,0을 누르면 된다.

그런데 얼마 전, 꿍은 알람시계를 맞추다가 시각을 잘못 입력했는데 화면에 나타나는 시간은 24로 나눈 나머지라는 것을 알게됐다. 마찬가지로 분 역시 60으로 나눈 나머지가 화면에 나타나는 사실을 알게됐다. 예를 들어 66:79로 시각을 잘못 입력했어도 실제로 화면에는 18:19로 나타난다는 것이다.

꿍은 매우 게을러서 원하는 알람시각을 맞추는데 최소한의 노력만 하고싶다. 그래서 여러분들은 꿍이 어떻게 하면 최소한의 노력을 들여서 원하는 시각으로 알람을 맞출 수 있을지 알아내는 프로그램을 만들어야 한다.

키보드는 위와 같이 생겼고 키 a에서 키 b로 이동할 때 필요한 노력은 다음과 같다.

effort(a,b) = |xa-xb|+|ya-yb|

여기서 (xa, ya) 와 (xb, yb)는 키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을 붙여야 한다.

예제 입력 1

14:19

예제 출력 1

14:79
W3sicHJvYmxlbV9pZCI6IjMxNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NGNcdWI3OGNcdWMyZGNcdWFjYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ1NzhcdWI0ZGNcdWQzZjBcdWM3M2NcdWI4NWMgXHVjNTRjXHViNzhjXHVjMmRjXHVhY2M0XHViOTdjIFx1YzEyNFx1YzgxNVx1ZDU2MCBcdWI1NGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YmQ4NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgNFx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQwYTRcdWJjZjRcdWI0ZGNcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM2YjBcdWI5YWNcdWFjMDAgMTI6MzBcdWM3M2NcdWI4NWMgXHVjNTRjXHViNzhjXHVjNzQ0IFx1YzEyNFx1YzgxNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTRcdWJhNzQgMSwyLDMsMFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDE4XHVhY2UwIDlcdWMyZGMzMFx1YmQ4NCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YjllOCBcdWM1NWVcdWM1ZDAgMFx1Yzc0NCBcdWJkOTlcdWM1ZWMgMCw5LDMsMFx1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjBcdWIzNzAgXHVjNWJjXHViOWM4IFx1YzgwNCwgXHVhZmNkXHVjNzQwIFx1YzU0Y1x1Yjc4Y1x1YzJkY1x1YWNjNFx1Yjk3YyBcdWI5ZGVcdWNkOTRcdWIyZTRcdWFjMDAgXHVjMmRjXHVhYzAxXHVjNzQ0IFx1Yzc5OFx1YmFiYiBcdWM3ODVcdWI4MjVcdWQ1ODhcdWIyOTRcdWIzNzAgXHVkNjU0XHViYTc0XHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMjRcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhYzhjXHViNDEwXHViMmU0LiBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgXHViZDg0IFx1YzVlZFx1YzJkYyA2MFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHVhYzAwIFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxMFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCA2Njo3OVx1Yjg1YyBcdWMyZGNcdWFjMDFcdWM3NDQgXHVjNzk4XHViYWJiIFx1Yzc4NVx1YjgyNVx1ZDU4OFx1YzViNFx1YjNjNCBcdWMyZTRcdWM4MWNcdWI4NWMgXHVkNjU0XHViYTc0XHVjNWQwXHViMjk0IDE4OjE5XHViODVjIFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWZjZFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVhYzhjXHVjNzQ0XHViN2VjXHVjMTFjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM1NGNcdWI3OGNcdWMyZGNcdWFjMDFcdWM3NDQgXHViOWRlXHVjZDk0XHViMjk0XHViMzcwIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWIxNzhcdWI4MjVcdWI5Y2MgXHVkNTU4XHVhY2UwXHVjMmY2XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNWVjXHViN2VjXHViZDg0XHViNGU0XHVjNzQwIFx1YWZjZFx1Yzc3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTU4XHViYTc0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWIxNzhcdWI4MjVcdWM3NDQgXHViNGU0XHVjNWVjXHVjMTFjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDFcdWM3M2NcdWI4NWMgXHVjNTRjXHViNzhjXHVjNzQ0IFx1YjlkZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHVjNzQ0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvYWxhcm0ucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDBhNFx1YmNmNFx1YjRkY1x1YjI5NCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWNiY1x1YWNlMCBcdWQwYTQgYVx1YzVkMFx1YzExYyBcdWQwYTQgYlx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIxNzhcdWI4MjVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+ZWZmb3J0KGEsYikgPSB8eDxzdWI+YTxcL3N1Yj4teDxzdWI+YjxcL3N1Yj58K3x5PHN1Yj5hPFwvc3ViPi15PHN1Yj5iPFwvc3ViPnw8XC9wPlxyXG5cclxuPHA+XHVjNWVjXHVhZTMwXHVjMTFjICh4PHN1Yj5hPFwvc3ViPiwgeTxzdWI+YTxcL3N1Yj4pIFx1YzY0MCAoeDxzdWI+YjxcL3N1Yj4sIHk8c3ViPmI8XC9zdWI+KVx1YjI5NCBcdWQwYTRhLCBiXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1Y2NiNCBcdWIxNzhcdWI4MjVcdWM3NTggXHVkNTY5XHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMGE0XHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVkMGE0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMTc4XHViODI1LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDBhNFx1YzVkMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1ZDBhNFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjE3OFx1YjgyNSwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWQwYTRcdWM1ZDBcdWMxMWMgXHViMTI0IFx1YmM4OFx1YzlmOCBcdWQwYTRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIxNzhcdWI4MjVcdWM3NTggXHVjMTM4IFx1YWMxMlx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDIyOjQ1XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODA0XHVjY2I0IFx1YjE3OFx1YjgyNVx1Yzc1OCBcdWFjMTJcdWM3NDAgZWZmb3J0KDIsMikrZWZmb3J0KDIsNCkrZWZmb3J0KDQsNSk9MCsyKzE9My4gXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IEhIOk1NIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWMxMjRcdWM4MTVcdWQ1NThcdWFjZTAgXHVjMmY2XHVjNzQwIFx1YzJkY1x1YWMwMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIwOTggXHViZDg0XHVjNzc0IFx1ZDU1YyBcdWM3OTBcdWI5YWNcdWMyMThcdWI3N2NcdWJhNzQgXHVjMTIwXHVkNTg5XHVkNTU4XHViMjk0IDBcdWM3NzQgXHViZDk5XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTI0XHVjODE1XHVkNTU4XHVhY2UwIFx1YzJmNlx1Yzc0MCBcdWMyZGNcdWFjMDFcdWM3NDAgMDA6MDB+MjM6NTkgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgSEg6TU0gXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWM3OTBcdWI5YWNcdWM3NTggXHVjMjE4XHViNzdjXHViYTc0IFx1YzEyMFx1ZDU4OVx1ZDU1OFx1YjI5NCAwXHVjNzQ0IFx1YmQ5OVx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE1NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImFsYXJtIiwiZGVzY3JpcHRpb24iOiI8cD5XaGVuIHdlIHNldCB0aGUgYWxhcm0gb24gb3VyIG1vYmlsZSBwaG9uZSwgd2UgdXNlIHRoZSBrZXlib2FyZCB0byBlbnRlciBmb3VyIGRpZ2l0cyAmbmRhc2g7IHRoZSBob3VycyBhbmQgdGhlIG1pbnV0ZXMuIEZvciBleGFtcGxlLCBpZiB0aGUgZGVzaXJlZCB0aW1lIGlzIDEyOjMwLCB3ZSBwcmVzcyB0aGUgZGlnaXRzIDEsIDIsIDMgYW5kIDAuIE9uZS1kaWdpdCBudW1iZXJzIGFyZSBlbnRlcmVkIHdpdGggdGhlIGxlYWRpbmcgemVybyAoZm9yIGV4YW1wbGUsIHRoZSBudW1iZXIgOSBpcyBlbnRlcmVkIGJ5IHB1bmNoaW5nIGluIDA5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U29tZSB0aW1lIGFnbywgb3VyIGZyaWVuZCBNaXJrbyBlbnRlcmVkIHRoZSB3cm9uZyB0aW1lIGFuZCBub3RpY2VkIHRoYXQgdGhlIGhvdXJzIGRpc3BsYXllZCBvbiB0aGUgc2NyZWVuIGFyZSBhY3R1YWxseSB0aGUgcmVtYWluZGVyIG9mIHRoZSBob3VycyBlbnRlcmVkIGRpdmlkZWQgYnkgMjQuIFNpbWlsYXJseSwgbWludXRlcyBkaXNwbGF5ZWQgb24gdGhlIHNjcmVlbiBhcmUgdGhlIHJlbWFpbmRlciBvZiB0aGUgbWludXRlcyBlbnRlcmVkIGRpdmlkZWQgYnkgNjAuIEZvciBleGFtcGxlLCBpZiBoZSBwdW5jaGVzIGluIDY2Ojc5LCB0aGUgZGlzcGxheWVkIHRpbWUgd2lsbCBiZSAxODoxOS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gaXMgdmVyeSBsYXp5IHNvIGhlIHdhbnRzIHRvIHVzZSBhcyBsaXR0bGUgZWZmb3J0IGFzIHBvc3NpYmxlIHRvIG9idGFpbiB0aGUgcmVxdWlyZWQgdGltZS4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgd2hhdCB0aW1lIHNob3VsZCBiZSBlbnRlcmVkIHNvIHRoYXQgdGhlIGNvcnJlY3QgdGltZSBpcyBkaXNwbGF5ZWQsIGFuZCB0aGUgbWluaW11bSBwb3NzaWJsZSB0b3RhbCBlZmZvcnQgaXMgdXNlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvYWxhcm0ucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMxcHg7IHdpZHRoOjExMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBlZmZvcnQgbmVlZGVkIGZvciB0aGUgZmluZ2VyIHRvIG1vdmUgZnJvbSB0aGUga2V5IGEgdG8gdGhlIGtleSBiIGlzOiZuYnNwOzxcL3A+XHJcblxyXG48cD5lZmZvcnQoYSxiKSA9IHx4PHN1Yj5hPFwvc3ViPi14PHN1Yj5iPFwvc3ViPnwrfHk8c3ViPmE8XC9zdWI+LXk8c3ViPmI8XC9zdWI+fCZuYnNwOzxcL3A+XHJcblxyXG48cD53aGVyZSAoeDxzdWI+YTxcL3N1Yj4sIHk8c3ViPmE8XC9zdWI+KSBhbmQgKHg8c3ViPmI8XC9zdWI+LCB5PHN1Yj5iPFwvc3ViPikgYXJlIHRoZSByb3ctY29sdW1uIGNvb3JkaW5hdGVzIG9mIHRoZSBrZXlzIGEgYW5kIGIgaW4gdGhlIGtleWJvYXJkIGxheW91dCBnaXZlbiBpbiB0aGUgYWJvdmUgZmlndXJlLiBUaGUgdG90YWwgZWZmb3J0IGlzIGRlZmluZWQgYXMgdGhlIHN1bSBvZiB0aHJlZSB2YWx1ZXM6IGVmZm9ydCB0byBtb3ZlIGZyb20gdGhlIGZpcnN0IHRvIHRoZSBzZWNvbmQgZGlnaXQsIGVmZm9ydCB0byBtb3ZlIGZyb20gdGhlIHNlY29uZCBkaWdpdCB0byB0aGUgdGhpcmQgZGlnaXQsIGFuZCBlZmZvcnQgdG8gbW92ZSBmcm9tIHRoZSB0aGlyZCBkaWdpdCB0byB0aGUgZm9ydGggZGlnaXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0b3RhbCBlZmZvcnQgZm9yIHRvIGVudGVyIDIyOjQ1IGlzIGVmZm9ydCgyLDIpK2VmZm9ydCgyLDQpK2VmZm9ydCg0LDUpPTArMisxPTMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IElmIHRoZXJlIGFyZSBtdWx0aXBsZSBzb2x1dGlvbnMsIG91dHB1dCB0aGUgZWFybGllc3QgdGltZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBkZXNpcmVkIHRpbWUgaW4gdGhlIGZvcm1hdCBISDpNTS4gT25lLWRpZ2l0IG51bWJlcnMgd2lsbCBiZSB3cml0dGVuIHdpdGggdGhlIGxlYWRpbmcgemVyby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGRlc2lyZWQgdGltZSBpcyB2YWxpZCBhbmQgYmV0d2VlbiAwMDowMCBpIDIzOjU5LCBpbmNsdXNpdmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBjb3JyZWN0IHNvbHV0aW9uIGluIHRoZSBmb3JtYXQgSEg6TU0uIE9uZS1kaWdpdCBudW1iZXJzIHNob3VsZCBiZSB3cml0dGVuIHdpdGggdGhlIGxlYWRpbmcgemVyby48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=