描述

给定一个字符串，按以下规则构造并输出最终字符串：

1. 将大写字母改为小写字母，并删去所有非字母字符。
2. 找出所有首次出现的字母，并按照字母顺序进行排列。
3. 将排列好的字母加到新字符串的末尾，并从原字符串中删除这些字母。
4. 重复步骤 2 和步骤3 ，直至将原字符串全部清空。
5. 删除相邻的重复字母，然后输出新字符串。(比如 "bboooo" 变为"bo").

例如，字符串“A good sorting algorithm.” 按照如下方式进行排列： 第 1 步: 新字符串: adghilmnorst. 剩余字符串: oogagorit 第 2 步: 新字符串: adghilmnorstagiort 剩余字符串: ogo 第 3 步: 新字符串: adghilmnorstagiortgo 剩余字符串: o 第 4 步: 新字符串: adghilmnorstagiortgoo 剩余字符串: 输出: adghilmnorstagiortgo

输入输出格式

输入

一行字符串，长度不超过 100，可能包含空格、标点、数字、大小写字母等任意 ASCII 字符。

输出

按上述规则处理后得到的字符串（已去除相邻重复字符）。

样例

A good sorting algorithm.

adghilmnorstagiortgo

限制

• 输入字符串长度 ≤ 100；
• 时间限制：1 秒；
• 空间限制：64 MB；
• 只含 ASCII 字符，无需考虑 Unicode。