Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9 (inclusive), generate all possible letter combinations that the number could represent according to the classic mobile phone keypad. The mapping is given by the following:

$$2: abc\\ 3: def\\ 4: ghi\\ 5: jkl\\ 6: mno\\ 7: pqrs\\ 8: tuv\\ 9: wxyz $$

Your task is to generate all combinations in the order they are produced by backtracking and output them separated by a single space. If the input is empty, output an empty line.

inputFormat

The input consists of a single line containing a string of digits (from 2 to 9). The string can be empty.

outputFormat

Output a single line containing all possible letter combinations separated by a space. If no combinations exist (i.e. empty input), output an empty line.## sample

23

ad ae af bd be bf cd ce cf