Phone Number Letter Combinations

Given a string of digits representing a phone number on a classic mobile numeric keypad, return all possible letter combinations that the phone number could represent. The mapping is given by: \(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 string is empty or contains digits (like 1 or 0) that do not map to any letters, the output should be empty.

inputFormat

The input consists of a single line containing a string \(D\) of digits (0-9).

outputFormat

Print each valid letter combination on a separate line (in the order generated by a depth-first search). If no combination is possible, output nothing.

23

ad
ae
af
bd
be
bf
cd
ce
cf