Digit-to-Letter Transformations

You are given a string s consisting of digits and lowercase letters. For every digit in the string, you have two options:

• Leave the digit as is.
• Transform the digit d into a letter using the rule: \(\text{letter} = \text{chr}('a' + d)\). For example, digit '0' transforms into 'a', '1' into 'b', etc.

Your task is to generate all possible transformations of the string, where each digit either stays the same or is replaced by its corresponding letter. The final list of strings should be output in lexicographical order.

Note: Non-digit characters remain unchanged.

inputFormat

The input consists of a single line containing the string s. The string may contain both digits and lowercase letters.

outputFormat

Output all possible transformation strings in lexicographical order on a single line, separated by a single space.

## sample

2

2 c

</p>