Phone Number Letter Combinations

Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent according to the standard phone number mapping. The mapping is defined as: $$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 input digit string could represent. The order of the combinations should follow the natural recursive order as generated by a typical backtracking algorithm.

inputFormat

The input consists of a single line read from stdin that contains a non-empty string of digits (each digit is between 2 and 9). If the input string is empty, the program should produce no output.

outputFormat

Output all possible letter combinations corresponding to the input digits on stdout. The combinations should be printed in one line, separated by a single space. There should be no trailing spaces.

23

ad ae af bd be bf cd ce cf