Capitalization Subsets

You are given a string s containing only alphabetical characters. Your task is to generate all possible strings by changing the case of each character. For each character in the string, you can choose either its uppercase form or its lowercase form. Output all the possible strings in lexicographical order (i.e. dictionary order, where uppercase letters are considered smaller than lowercase letters according to their ASCII values).

For example, given s = "ab", the possible strings are:

• "AB"
• "Ab"
• "aB"
• "ab"

Note: Use LaTeX formatting for formulas if needed. In this problem, if you want to denote the total number of combinations mathematically, you can use the formula: \(2^n\), where \(n\) is the length of the string.

inputFormat

The input consists of a single line containing the string s.

Input Format:

s

outputFormat

Output all possible strings generated as described above, each on a separate line, sorted in lexicographical order.

Output Format:

result_1
result_2
... 
result_{2^n}

## sample

a

A
a

</p>