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. The digit-to-letter mapping follows the standard telephone keypad, where:

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

Your task is to implement a complete program that reads the input from stdin and writes the result to stdout. The output should list all possible combinations separated by a single space, in the order generated by a backtracking algorithm.

inputFormat

A single line containing a string consisting of digits from '2' to '9'.

outputFormat

Output all possible letter combinations separated by a space. If the input string is empty, output nothing.

23

ad ae af bd be bf cd ce cf