408781: GYM103316 H Temple Door

After journeying far and wide, Tang has finally made it to the legendary Fire Temple where he must speak with an ancient Avatar and learn the fate of the world. There's just one problem—the massive door into the inner sanctuary is sealed shut! Fortunately, it appears that there's a puzzle embedded in the door which, when solved, may trigger the unlocking mechanism.

There are six number dials embedded into the door, grouped into three pairs of digits, all separated by colons. The symbol of an hourglass engraved on a nearby wall indicates that the numbers refer to units of time—specifically, hours, minutes, and seconds, in the format $$$\texttt{hh:mm:ss}$$$.

Tang believes that if he sets the dials to show the time of a significant celestial event, then that will solve the puzzle and open the temple door. He has $$$N$$$ guesses about when that celestial event could be and wants to try them all. However, Tang notices that $$$D$$$ unique digits are missing from the dials, making it impossible to precisely set the dials to some of his guesses. Not to fear though, surely the ancient Fire Sages would have designed the door to accept the closest time setting possible that can be displayed on the dials.

Help Tang enter the inner sanctuary of the Fire Temple! For each time guess $$$g_i$$$ that Tang wants to try on the door, output the closest possible time that he will be able to display, given that some digits are missing from the dials.

The first line of input contains an integer $$$D$$$ ($$$1 \leq D \leq 9$$$) denoting the number of digits absent from the puzzle dials. The next line contains $$$D$$$ space-separated integers, sorted in increasing order, which are the digits not available on the six dials.

Then the third line of input contains an integer $$$N$$$ ($$$1 \leq N \leq 10^4$$$) denoting the number of time guesses Tang wants to make. $$$N$$$ lines follow, each containing a guess index $$$i$$$ followed by one of Tang's time guesses $$$g_i$$$ in the six-digit format $$$\texttt{hh:mm:ss}$$$.

For each of Tang's guesses in order, output one line containing the guess index $$$i$$$ followed by the closest possible time setting to $$$g_i$$$ that Tang will be able to input on the door, printed in the same format $$$\texttt{hh:mm:ss}$$$. In the case of a tie between closest settings, output the smaller time quantity.

Note, the values for hours, minutes, or seconds in Tang's guesses will lie in the range from $$$0$$$ to $$$59$$$, and similarly, no hours, minutes, or seconds value greater than $$$59$$$ may be set by Tang on the dials (the digits available on the individual dials prevent this).

2
8 9
4
0 38:15:51
1 32:06:35
2 23:31:47
3 04:05:47

0 37:57:57
1 32:06:35
2 23:31:47
3 04:05:47