1083 - 全排列V3
Description

给定一个由数字和大小写字母组成的字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。请你按字典序升序列出所有可能得到的字符串。

例如S="a2b1",可能得到的字符串有"a2b1"、"a2B1"、"A2b1"、"A2B1",依次输出即可。


Input
一行输入一个字符串S。其中S中的元素仅可能为大小写字母或数字。


Output
每行输出一个可能得到的字符串。请按照字典序升序输出。


Examples

Input

a2b1

Output

A2B1
A2b1
a2B1
a2b1
Hint
对于100%的数据,1≤|S|≤15;


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 54
通过次数 31