Letter Combinations

Given a string s containing digits from 2 to 9 inclusive, write a program to return all possible letter combinations that the number could represent according to the mapping of digits to letters on a telephone keypad (image below). The letter combinations should be printed in lexicographical order.
notion image

Input

The input consists of a single line containing the string s (1 ≤ |s| ≤ 10), where |s| represents the length of the string. The string s consists of digits from 2 to 9 inclusive.

Output

Output all possible letter combinations that can be formed by the given s, with each combination printed on a separate line. The letter combinations should be printed in lexicographical order.

Examples

Input
Output
25
aj ak al bj bk bl cj ck cl

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 7 MB

To check your solution you need to sign in
Sign in to continue