Letter Combinations of a Phone Number

You are given a string of digits (from 2 to 9) representing a phone number. Each digit maps to a set of letters as on a traditional telephone keypad. The mapping is given by:

\(2 \to abc,\quad 3 \to def,\quad 4 \to ghi,\quad 5 \to jkl,\quad 6 \to mno,\quad 7 \to pqrs,\quad 8 \to tuv,\quad 9 \to wxyz\)

Your task is to generate and print all possible letter combinations that the number could represent. If the input is an empty string, no output should be produced.

The combinations should be generated using a backtracking approach. Each valid combination must be printed on a new line in the order they are generated, which will be in lexicographical order.

inputFormat

The input consists of a single line containing a string of digits. The digits will only be between 2 and 9. An empty string is also a valid input.

outputFormat

If there are valid letter combinations, print each combination on a separate line to standard output. If the input is an empty string, do not print anything.

## sample

23

ad
ae
af
bd
be
bf
cd
ce
cf

</p>