Letter Combinations of a Phone Number

Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. Each digit maps to a set of letters on a telephone keypad: (2\to abc), (3\to def), (4\to ghi), (5\to jkl), (6\to mno), (7\to pqrs), (8\to tuv), and (9\to wxyz). If the input string is empty, no output should be produced. In general, for an input of length (n), the total number of combinations is given by (\prod_{i=1}^{n}|mapping(digit_i)|).

inputFormat

A single line containing a string of digits between 2 and 9 (possibly empty).

outputFormat

Print all possible letter combinations in the order they are generated (which is lexicographical according to the keypad mapping), separated by a single space. If the input is empty, print nothing.## sample

23

ad ae af bd be bf cd ce cf