Letter Combinations of a Phone Number

Given a mapping of digits to letters (as on telephone buttons), write a program that returns all possible letter combinations that the number could represent. The digits are mapped as follows:

(2:) a, b, c
(3:) d, e, f
(4:) g, h, i
(5:) j, k, l
(6:) m, n, o
(7:) p, q, r, s
(8:) t, u, v
(9:) w, x, y, z

If the input string is empty, output an empty line. The output should list the combinations in lexicographical order separated by a single space.

inputFormat

The input is read from standard input. It consists of a single line containing a string of digits in the range 2-9.

outputFormat

Output to standard output a single line containing all possible letter combinations separated by a single space. If there are no combinations (empty input), output an empty line.## sample

2

a b c