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 based on the mapping of digits to letters. The mapping is as follows: \(2: \text{abc},\ 3: \text{def},\ 4: \text{ghi},\ 5: \text{jkl},\ 6: \text{mno},\ 7: \text{pqrs},\ 8: \text{tuv},\ 9: \text{wxyz}\).

If the input is an empty string, output an empty line.

inputFormat

A single line from standard input containing a string of digits (from 2 to 9).

outputFormat

Print all possible letter combinations in sorted lexicographical order, separated by spaces. If there are no combinations, print an empty line.## sample

23

ad ae af bd be bf cd ce cf