Phone Keypad Letter Combinations

Given a string of digits from 2 to 9, return all possible letter combinations that the number could represent according to the mapping of a traditional phone keypad. The mapping is as follows: (2 \to ABC), (3 \to DEF), (4 \to GHI), (5 \to JKL), (6 \to MNO), (7 \to PQRS), (8 \to TUV), (9 \to WXYZ).

If the input string is empty, the output should be empty. The combinations should be output in the order they are generated using a standard backtracking recursive approach.

inputFormat

The input consists of a single line containing a string of digits (only from 2 to 9).

outputFormat

Output all possible letter combinations corresponding to the input digits, separated by a single space. If the input is empty, output an empty line.## sample

23

AD AE AF BD BE BF CD CE CF