Mysterious number

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka, as befits all representatives of the fair sex, loves to speak in riddles. This time too, Marichka planned to write a note to Zenik with her favorite number, but she couldn’t resist, and replaced some digits in the number with asterisks (the * symbol).

When Zenik received the note, as usual, he didn’t understand what it meant and what hidden meaning was in this message. Therefore, he decided to determine the minimum and maximum possible number Marichka wanted to tell him.

Note that each asterisk must be replaced by some digit. Also, the numbers must not contain leading zeros. That is, the first digit of the number must not be 0.

Input

The single line gives a single string — a sequence of digits and asterisks.

Output

In the single line, print two positive integers — the minimum and maximum possible number that Marichka wanted to communicate.

Constraints

The length of the number does not exceed 9,

it is guaranteed that the first character is not 0.

Samples