Letter Combinations of a Phone Number

You are given a string containing digits from 2 to 9. Each digit maps to a set of letters as in a standard telephone keypad:

\(2: abc\), \(3: def\), \(4: ghi\), \(5: jkl\), \(6: mno\), \(7: pqrs\), \(8: tuv\), \(9: wxyz\).

Your task is to generate all possible letter combinations that the number could represent. If the input string is empty, you should output nothing.

inputFormat

The input consists of a single line containing a string of digits. Each digit is in the range 2-9.

outputFormat

Output all possible letter combinations that the given number could represent. The combinations should be printed on a single line separated by a single space, in the order generated by a standard Cartesian product of the mapped characters.## sample

23

ad ae af bd be bf cd ce cf