ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2016

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Faulty dial

Time limit: 2.0 second
Memory limit: 256 MB
Pavel has not played ACM for ages, nor does he train teams, nor prepare problems. The thing is that there are much more global issues that concern him — Pavel ponders on education as a whole. His thoughts are always busy with this, but the problem is that various insignificancies distract him all the time! Let us look at a microwave oven, for example. Firstly, it does not allow to set exact time in seconds for warming up food, whilst seconds play the key role in this issue! That is why Pavel has to set the minimal available time option exceeding the time needed, and to keep an eye on the timer in order to switch the oven off at the right moment. Secondly, as it came out, the oven’s dial is faulty — random digit segments may be not displayed when indicating time. As a result it becomes nearly impossible to stop the oven at the correct moment of time — with faulty dial Pavel is unable to read what the timer is displaying at each moment.
Help Pavel — write a program recovering real timer data.

Input

The first line contains n (1 ≤ n ≤ 100) — the number of timer readings recorded by Pavel. Next lines represent n timer readings. Each reading is described with 3 lines 17 characters of length each, and encodes a timer value in MM:SS format (minutes and seconds).
Each timer digit is encoded in 9 characters: three characters in each of 3 strings. Higher order digit for minutes is encoded with characters in the positions 1−3 (here and further positions are enumerated starting with 1), lower order digit for minutes — with characters 5−7, higher order digit for seconds — with characters in the positions 11−13, lower order digit for seconds — with characters 15−17. Characters ’_’ (underscore, decimal ASCII code 95), ’|’ (vertical bar, decimal ASCII code 124) and ’.’ (full stop, decimal ASCII code 46) are used to encode digits. Code descriptions for all nine digits (with all segments displayed) are listed below.
._. ... ._. ._. ... ._. ._. ._. ._. ._.
|.| ..| ._| ._| |_| |_. |_. ..| |_| |_|
|_| ..| |_. ._| ..| ._| |_| ..| |_| ._|
Character ’*’ (asterisk, decimal ASCII code 42) stands in the ninth position at the timer’s readings lines 2 and 3,and all positions not mentioned above contain full stops.
If a segment of a digit is not displayed at the dial, this character will be replaced with a full stop in its encoded representation (segments encoded with full stop are always displayed correctly).

Output

Output n MM:SS formatted lines representing the recovered sequence of timer’s values. Line i must correspond with the i-th reading and has to be a valid time value between 00:00 and 59:59. Each subsequent value must be strictly less than the preceding one. If several answers exist, output any of them. It is guaranteed that there is at least one consistent sequence.

Sample

inputoutput
2
._..._........._.
|...._|.*...|.._|
|_|.._..*...|.|..
....._....._..._.
|.|...|.*.|.|.._.
|.|.|_..*.|_|.._.
03:12
00:05
Problem Author: Pavel Egorov, prepared by Ivan Burmistrov
To submit the solution for this problem go to the Problem set: 2081. Faulty dial