题目描述

老师念出一个单词的每个字母，学生们拼写单词（只写大写字母）。每听到一个字母，可以将该字母写在之前已经写好字母的最前面或最后面。例如，老师念的单词为 CAB, 学生听到 C，就写下 C；听到 A，那就有 $2$ 种写法，结果分别为 CA 和 AC；听到 B，那就有 $4$ 种写法，结果分别为 BCA, CAB, BAC, ACB。

现在想知道这些可能的写法中字典序最大的那个拼写结果。前面例子中 CAB 就是那个想要知道的拼写结果。

输入格式

一个单词（长度不超过1000），包含大小写字母。

输出格式

输出字典序最大拼写结果，注意学生听不出大小写，一律写大写字母。

测试样例

CAB

CAB

a

A

Programming

RRPOGAMMING