Description
In a certain gambling town, dice have become so popular that they are even used to dial phone numbers. Each face of a six-faced die has a single digit printed on it. The dialing process works as follows. Given a phone number, which is simply a string of digits, one dials the first digit of the number by placing the die on the dialing board. The digit on the bottom face of the die is automatically dialed. To dial the next digit, the die is turned over so that one of the adjacent sides is now on the bottom. Again the digit on the new bottom face is dialed. The procedure continues until all the digits of the target phone number are dialed.
Unfortunately, as you might imagine, there are quite a few problems with this dialing method. First, the standard dice (with faces labeled 1 through 6) are not capable of dialing certain crucial numbers such as 911. To remedy this situation, people were allowed to “program” their dice by choosing any digits to place on the faces (two faces may contain the same digit).
As it turns out, this remedy still does not fully solve the problem, since no die can dial 1234567 (there are 7 digits, but only 6 sides on a die). When this was discovered, the people threw up their hands along with their dice and went back to their gambling. A few days of mulling over the problem lead to a new solution: people would be only required to dial a number that has small discrepancy with respect to the number that they really want to dial. The discrepancy between the two numbers is the minimum number of additions, deletions, or substitutions of digits required to transform one number into the other. For example, the discrepancy between 91 and 911 is 1, between 12399 and 1499 is 2, etc.
People often wondered about the optimal way to program their dice. Your task is to write a program to help them out. Given a target number N, program a die so that the die can be used to dial some number N', where the discrepancy between N and N' is minimized. Note that the die can be programmed with any digits, regardless of the target phone number.
(You might notice other difficulties with this dialing system, but those are to be solved in a future task.)
Input
Each line of the input contains exactly one phone number of length 1 ≤ N ≤ 100. While the number may contain any digits from 0 to 9, a given number contains at most 7 distinct digits.
Output
For each number, output the minimum discrepancy that can be obtained by any die and the 6 digits on the die that achieves that discrepancy. Sort the digits in ascending order. If there are ties, print out the sequence of digits that is lexicographically smallest.
Sample Input
000
000112222
1233456
Sample Output
Dice 1: discrepancy is 0, digits used: 0 0 0 0 0 0
Dice 2: discrepancy is 0, digits used: 0 0 1 1 2 2
Dice 3: discrepancy is 1, digits used: 1 2 3 3 4 5
