시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB21413813069.519%

문제

코레스코 콘도의 각 방에는 디지털 시계가 설치되어 있다. 디지털 시계에는 4개의 숫자가 표현될 수 있으며, 이것은 'hh:mm'의 형식으로 시간을 표현한다. 즉, 앞의 두 자리는 시간을, 뒤의 두 자리는 분을 표현한다. 시간은 00:00부터 23:59까지의 24시 체계를 쓴다.

디지털 시계의 각 숫자는 15개의 발광다이오드로 표현이 된다. 5x3형태로 배열되어 있는 발광 다이오드들 중 특정한 몇 칸이 켜져서 숫자를 나타내는 것이다. 다음과 같다. '#'은 불이 켜져 있는 다이오드를, '.'은 그렇지 않은 다이아몬드를 나타낸다.

###  ..#  ###  ###  #.#  ###  ###  ###  ###  ###
#.#  ..#  ..#  ..#  #.#  #..  #..  ..#  #.#  #.#
#.#  ..#  ###  ###  ###  ###  ###  ..#  ###  ###
#.#  ..#  #..  ..#  ..#  ..#  #.#  ..#  #.#  ..#
###  ..#  ###  ###  ..#  ###  ###  ..#  ###  ###

그런데 투숙객이 아침에 일어나서 시계를 보니 몇 개의 발광다이오드가 고장나 불이 켜지지 않은 것을 발견했다. (켜지지 않아야 하는 발광다이오드가 켜진 경우는 없다)모든 투숙객은 자신이 부지런하고 믿는 사람들이기 때문에 투숙객은 가능하면 현재 시각을 빠른 시각(00:00에 가까운 시각이 늘 빠른 시각이다)으로 생각하고 싶다.

일부 발광다이오드가 고장난 디지털 시계의 네 숫자가 주어졌을 때, 이러한 배치가 가능한 가장 빠른 시각을 구하는 프로그램을 작성하시오.

입력

각 줄에는 15개의 문자가 다음과 같이 주어진다. 네 번째 문자마다 공백이 한 칸씩 주어지고, 그 외에는 '#' 또는 '.'이 주어진다. 입력되는 순서는 시계의 배치된 순서와 같다.

출력

이러한 배치가 가능한 가장 빠른 시각을 출력한다.

예제 입력 1

#.# ... ... #..
#.# ... ... #..
#.# ### ### ###
#.# #.. ..# ..#
### ### ### ..#

예제 출력 1

02:34

예제 입력 2

### ### ..# ...
... #.# #.# #.#
### #.# .#. .#.
#.. #.# ..# ..#
### #.# ..# ###

예제 출력 2

20:48

예제 입력 3

#.. #.# #.# .#.
..# #.. ... #..
#.# .## ### .##
..# #.# ... ...
#.# ### ##. ###

예제 출력 3

06:25
W3sicHJvYmxlbV9pZCI6IjIwODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWFjYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2Y1NFx1YjgwOFx1YzJhNFx1Y2Y1NCBcdWNmNThcdWIzYzRcdWM3NTggXHVhYzAxIFx1YmMyOVx1YzVkMFx1YjI5NCBcdWI1MTRcdWM5YzBcdWQxMzggXHVjMmRjXHVhY2M0XHVhYzAwIFx1YzEyNFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjUxNFx1YzljMFx1ZDEzOCBcdWMyZGNcdWFjYzRcdWM1ZDBcdWIyOTQgNFx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNDVjXHVkNjA0XHViNDIwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCAmIzM5O2hoOm1tJiMzOTtcdWM3NTggXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQ0NWNcdWQ2MDRcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjNTVlXHVjNzU4IFx1YjQ1MCBcdWM3OTBcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0LCBcdWI0YTRcdWM3NTggXHViNDUwIFx1Yzc5MFx1YjlhY1x1YjI5NCBcdWJkODRcdWM3NDQgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWMyZGNcdWFjMDRcdWM3NDAgMDA6MDBcdWJkODBcdWQxMzAgMjM6NTlcdWFlNGNcdWM5YzBcdWM3NTggMjRcdWMyZGMgXHVjY2I0XHVhY2M0XHViOTdjIFx1YzRmNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNTE0XHVjOWMwXHVkMTM4IFx1YzJkY1x1YWNjNFx1Yzc1OCBcdWFjMDEgXHVjMjJiXHVjNzkwXHViMjk0IDE1XHVhYzFjXHVjNzU4IFx1YmMxY1x1YWQxMVx1YjJlNFx1Yzc3NFx1YzYyNFx1YjRkY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWM3NzQgXHViNDFjXHViMmU0LiA1eDNcdWQ2MTVcdWQwZGNcdWI4NWMgXHViYzMwXHVjNWY0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWJjMWNcdWFkMTEgXHViMmU0XHVjNzc0XHVjNjI0XHViNGRjXHViNGU0IFx1YzkxMSBcdWQyYjlcdWM4MTVcdWQ1NWMgXHViYTg3IFx1Y2U3OFx1Yzc3NCBcdWNmMWNcdWM4MzhcdWMxMWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuICYjMzk7PGNvZGU+IzxcL2NvZGU+JiMzOTtcdWM3NDAgXHViZDg4XHVjNzc0IFx1Y2YxY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHViMmU0XHVjNzc0XHVjNjI0XHViNGRjXHViOTdjLCAmIzM5Ozxjb2RlPi48XC9jb2RlPiYjMzk7XHVjNzQwIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3NDAgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHByZSBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cclxuIyMjICAuLiMgICMjIyAgIyMjICAjLiMgICMjIyAgIyMjICAjIyMgICMjIyAgIyMjXHJcbiMuIyAgLi4jICAuLiMgIC4uIyAgIy4jICAjLi4gICMuLiAgLi4jICAjLiMgICMuI1xyXG4jLiMgIC4uIyAgIyMjICAjIyMgICMjIyAgIyMjICAjIyMgIC4uIyAgIyMjICAjIyNcclxuIy4jICAuLiMgICMuLiAgLi4jICAuLiMgIC4uIyAgIy4jICAuLiMgICMuIyAgLi4jXHJcbiMjIyAgLi4jICAjIyMgICMjIyAgLi4jICAjIyMgICMjIyAgLi4jICAjIyMgICMjIzxcL3ByZT5cclxuXHJcbjxwPlx1YWRmOFx1YjdmMFx1YjM3MCBcdWQyMmNcdWMyMTlcdWFjMWRcdWM3NzQgXHVjNTQ0XHVjZTY4XHVjNWQwIFx1Yzc3Y1x1YzViNFx1YjA5OFx1YzExYyBcdWMyZGNcdWFjYzRcdWI5N2MgXHViY2Y0XHViMmM4IFx1YmE4NyBcdWFjMWNcdWM3NTggXHViYzFjXHVhZDExXHViMmU0XHVjNzc0XHVjNjI0XHViNGRjXHVhYzAwIFx1YWNlMFx1YzdhNVx1YjA5OCBcdWJkODhcdWM3NzQgXHVjZjFjXHVjOWMwXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjODNcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiAoXHVjZjFjXHVjOWMwXHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViYzFjXHVhZDExXHViMmU0XHVjNzc0XHVjNjI0XHViNGRjXHVhYzAwIFx1Y2YxY1x1YzljNCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0KVx1YmFhOFx1YjRlMCBcdWQyMmNcdWMyMTlcdWFjMWRcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YmQ4MFx1YzljMFx1YjdmMFx1ZDU1OFx1YWNlMCBcdWJiZmZcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQyMmNcdWMyMTlcdWFjMWRcdWM3NDAgXHVhYzAwXHViMmE1XHVkNTU4XHViYTc0IFx1ZDYwNFx1YzdhYyBcdWMyZGNcdWFjMDFcdWM3NDQgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwMSgwMDowMFx1YzVkMCBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjMmRjXHVhYzAxXHVjNzc0IFx1YjI5OCBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzAxXHVjNzc0XHViMmU0KVx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3N2NcdWJkODAgXHViYzFjXHVhZDExXHViMmU0XHVjNzc0XHVjNjI0XHViNGRjXHVhYzAwIFx1YWNlMFx1YzdhNVx1YjA5YyBcdWI1MTRcdWM5YzBcdWQxMzggXHVjMmRjXHVhY2M0XHVjNzU4IFx1YjEyNCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViN2VjXHVkNTVjIFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDFcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IDE1XHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMTI0IFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWI5YzhcdWIyZTQgXHVhY2Y1XHViYzMxXHVjNzc0IFx1ZDU1YyBcdWNlNzhcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWFkZjggXHVjNjc4XHVjNWQwXHViMjk0ICYjMzk7PGNvZGU+IzxcL2NvZGU+JiMzOTsgXHViNjEwXHViMjk0ICYjMzk7PGNvZGU+LjxcL2NvZGU+JiMzOTtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWI0MThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YzJkY1x1YWNjNFx1Yzc1OCBcdWJjMzBcdWNlNThcdWI0MWMgXHVjMjFjXHVjMTFjXHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHViYzMwXHVjZTU4XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjA4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNMT0NLIiwiZGVzY3JpcHRpb24iOiI8cD5PbmUgZGF5LCBEYXZlIG1hZGUgYSBkaWdpdGFsIGNsb2NrLiBFYWNoIG9mIGZvdXIgbnVtYmVycyBuZWVkZWQgdG8gZGlzcGxheSBhIHRpbWUgKGluIGhobW0gZm9ybWF0KSBvbiBpdCBpcyByZXByZXNlbnRlZCB3aXRoIDE1IHNtYWxsIHJlZCBMRUQgZGlvZGVzIGFycmFuZ2VkIGluIGEgNXgzIG1hdHJpeCBhcyBzaG93biBiZWxvdyAoJiMzOTsjJiMzOTsgcmVwcmVzZW50cyBsaXQgZGlvZGUsIGFuZCAmIzM5Oy4mIzM5OyB1bmxpdCBkaW9kZSkuPFwvcD5cclxuXHJcbjxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHJcbiMjIyAgLi4jICAjIyMgICMjIyAgIy4jICAjIyMgICMjIyAgIyMjICAjIyMgICMjI1xyXG4jLiMgIC4uIyAgLi4jICAuLiMgICMuIyAgIy4uICAjLi4gIC4uIyAgIy4jICAjLiNcclxuIy4jICAuLiMgICMjIyAgIyMjICAjIyMgICMjIyAgIyMjICAuLiMgICMjIyAgIyMjXHJcbiMuIyAgLi4jICAjLi4gIC4uIyAgLi4jICAuLiMgICMuIyAgLi4jICAjLiMgIC4uI1xyXG4jIyMgIC4uIyAgIyMjICAjIyMgIC4uIyAgIyMjICAjIyMgIC4uIyAgIyMjICAjIyM8XC9wcmU+XHJcblxyXG48cD5EYXZlIHNldCB0aGUgY29ycmVjdCB0aW1lIG9uIGhpcyBuZXcgY2xvY2sgYW5kLCBiZWluZyBleGhhdXN0ZWQgd2l0aCBlZmZvcnQgbmVlZGVkIHRvIG1ha2UgdGhlIGNsb2NrIHdlbnQgdG8gc2xlZXAuPFwvcD5cclxuXHJcbjxwPldoZW4gaGUgd29rZSB1cCBuZXh0IG1vcm5pbmcsIGhlIGxvb2tlZCBhdCBoaXMgbmV3IGNsb2NrIGFuZCBmb3VuZCBvdXQgdGhhdCBzb21lIG9mIGRpb2RlcyB3ZW50IG9mZi48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIGVhcmxpZXN0IHBvc3NpYmxlIHRpbWUgdGhhdCBjb3JyZXNwb25kcyB0byBEYXZlJnJzcXVvO3MgZmF1bHR5IGNsb2NrIGRpc3BsYXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBmaWxlIGNvbnRhaW5zIGZvdXIgNXgzIGdyb3VwcyBvZiBjaGFyYWN0ZXJzICYjMzk7PGNvZGU+IzxcL2NvZGU+JiMzOTsgYW5kICYjMzk7PGNvZGU+LjxcL2NvZGU+JiMzOTsgc2VwYXJhdGVkIGJ5IG9uZSBjb2x1bW4gb2Ygc3BhY2VzLiBUaG9zZSBmb3VyIGdyb3VwcyByZXByZXNlbnQgYXJyYW5nZW1lbnQgb2YgbGl0IGFuZCB1bmxpdCBkaW9kZXMgb2YgYSBmYXVsdHkgZGlzcGxheS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgZmlsZSBzaG91bGQgY29udGFpbiBkZXNpcmVkIHRpbWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==