Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent on a telephone keypad. Each digit maps to a set of letters as shown in the classical mapping:

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

The combinations should be output in lexicographical order. This problem tests your ability to use backtracking to explore all possible combinations. Input is read from standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The input consists of a single line containing a non-negative string of digits (each from 2 to 9). The string may be empty.

outputFormat

Output all possible letter combinations in lexicographical order, separated by a single space, on one line. If the input is empty, output an empty line.

## sample

23

ad ae af bd be bf cd ce cf

</p>