Phone Letter Combinations

Given a string of digits, generate all possible letter combinations that the number could represent based on a telephone keypad. The digit-to-letter mapping is given by the following relation: (2 \to {a,b,c}), (3 \to {d,e,f}), (4 \to {g,h,i}), (5 \to {j,k,l}), (6 \to {m,n,o}), (7 \to {p,q,r,s}), (8 \to {t,u,v}), and (9 \to {w,x,y,z}). If the input string is empty, the output should be empty. This problem can be solved efficiently using backtracking.

inputFormat

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

outputFormat

Print all possible letter combinations separated by a single space in one line to standard output (stdout). If there are no combinations (i.e. when the input is empty), output an empty line.## sample

2

a b c