Under construction

Still being built. Things may change

Flute

Interview

Time limit1sMemory limit512 MB

Summary
Given four scrambled lamp grids whose lit lamps may include burned-out (dark) ones, output the earliest valid time matching each grid as a digit pattern.
Level

Medium5 of 10

Topics
Implementation, Brute force, String
Solved
No attempts yet

Problem

Mirko has a digital clock that he recently built himself. Mirko's clock displays time in the form "hhmm", where hh and mm are the two-digit hour and minute. The earliest valid time in a day is "0000", and the latest is "2359". Each of the four digits on the clock is shown by a grid of red lamps arranged in 5 rows and 3 columns. Digits are shown by combinations of lit and unlit lamps as in the figure (the character "#" represents a lit lamp and the character "." represents an unlit lamp).

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

When Mirko woke up this morning, he felt a little strange and was gripped by a fear that he might have missed a prearranged private flute lesson. To make matters worse, he looked at the clock and discovered that the lit lamps did not show anything meaningful, and concluded that some lamps may have burned out overnight and no longer work. Feeling a strong desire to find out whether it was still early enough and whether there was a chance he could make it to the lesson, he wanted to find out how early the time could be.

Based on the appearance of the clock, determine the earliest possible time shown on the clock, assuming that zero, one, or more lamps have broken and gone dark.

Input

The input consists of five lines, each with exactly 15 characters: four grids of characters "#" and "." separated by a single column of space characters, representing the appearance of the clock (the arrangement of lit and unlit lamps on the clock).

Output

Print the requested time in the format "hh:mm", where hh and mm are the two-digit hour and minute.

Examples3

  1. Example 1

    Input
    #.# ... ... #..
#.# ... ... #..
#.# ### ### ###
#.# #.. ..# ..#
### ### ### ..#
    Expected output
    02:34

  2. Example 2

    Input
    ### ### ..# ...
... #.# #.# #.#
### #.# .#. .#.
#.. #.# ..# ..#
### #.# ..# ###
    Expected output
    20:48

  3. Example 3

    Input
    #.. #.# #.# .#.
..# #.. ... #..
#.# .## ### .##
..# #.# ... ...
#.# ### ##. ###
    Expected output
    06:25