单点时限: 2.0 sec
内存限制: 256 MB
老师念出一个单词 w 的每个字母，学生们拼写单词。每听到一个字母，可以将该字母写在之前已经写好字母的最前面或最后面。例如，老师念的单词 w 为 $CAB$, 学生听到 $C$，就写下 $C$ ；听到 $A$，那就有2种写法，结果分别为 $CA$ 和 $AC$ ；听到 $B$ ，那就有4种写法，结果分别为 $BCA$, $CAB$, $BAC$, $ACB$。
现在想知道这些可能的写法中字典序最大的那个拼写结果。前面例子中 $CAB$ 就是那个想要知道的拼写结果。
设 |w| 表示字符串长度，可能的拼写方法最多是 $2^{|w|-1}$ 。
一个单词 w $(1≤|w|≤1000)$ ，包含大小写字母。
一行中输出想要知道的拼写结果, 用大写字母输出。
CAB
CAB
a
A
Programming
RRPOGAMMING