Faded Time-Card Latest Punch

EasyStringEnumerationTime2 sample tests6 hidden tests

A factory's mechanical time clock stamps each worker's card with the current time in 12-hour format "HH:MM AM" or "HH:MM PM" (the hour is always printed with a leading zero, from "01" to "12"). After years of use, the ink ribbon has faded unevenly, so some of the printed characters — hour digits, minute digits, or the two letters of the AM/PM mark — have become illegible and are recorded as '?'. Every character that is still legible is guaranteed correct. Reconstruct the latest possible moment of the 12-hour cycle (treating "12:00 AM", i.e. midnight, as the earliest instant of the cycle and "11:59 PM" as the latest) that is consistent with every legible character, and print the reconstructed stamp in the same format.

Input format

A single line containing a string of exactly 8 characters in the form "HH:MM AP", where:

characters at positions 1 and 2 (the hour) are each a digit '0'-'9' or '?'
position 3 is always ':'
characters at positions 4 and 5 (the minute) are each a digit '0'-'9' or '?'
position 6 is always a single space
characters at positions 7 and 8 (the meridiem mark) are each 'A', 'P', or 'M', or '?'

Output format

A single line containing the reconstructed stamp, in the identical "HH:MM AP" format, representing the latest valid moment of the 12-hour cycle consistent with the input.

Constraints

The hour, when fully read, is guaranteed to form an integer between 1 and 12 inclusive, printed with a leading zero (e.g. "01", "12").
The minute, when fully read, is guaranteed to form an integer between 0 and 59 inclusive, printed with a leading zero.
The meridiem mark, when fully read, is guaranteed to be exactly "AM" or "PM".
The input is guaranteed to admit at least one assignment of the '?' characters that satisfies all of the above.

Examples

Example 1

Input

1?:?? ?M

Expected

11:59 PM

Explanation

The hour pattern "1?" restricted to a valid 1-12 hour (leading zero form) allows only "10", "11", or "12" (since "13" through "19" aren't valid 12-hour hours). The minute is fully free, so it can be maximized to "59". The meridiem pattern "?M" allows both "AM" and "PM". Comparing chronologically: among {10,11,12} paired with PM, the hour-of-day values are 22, 23, and 12 (noon) respectively — so "11 PM" (23) beats even "12 PM" (12, noon). Among {10,11,12} paired with AM the best is "11 AM" (11). PM wins overall, and within PM the best hour is 11. The latest valid stamp is "11:59 PM".

Example 2

Input

?2:00 AM

Expected

02:00 AM

Explanation

The hour pattern "?2" restricted to a valid 1-12 hour allows only "02" or "12" (values 2 and 12; a tens digit of 2-9 with units '2' would exceed 12). The minute is fixed at "00" and the meridiem is fixed at "AM". Converting to hour-of-day: "02" with AM gives 2, while "12" with AM gives 0 (midnight, the very earliest instant of the whole cycle). So hour "02" is later than hour "12" here, even though "12" is numerically the larger printed hour. The latest valid stamp is "02:00 AM".

Ready to solve this?