游园安排

题目描述

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。

小蓝是 L 星球游乐园的管理员，为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。

每个游客的名字由一个大写英文字母开始，后面跟 0 00 个或多个小写英文字母，游客可能重名。

小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，

在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。

一个名字 A AA 小于另一个名字 B BB 是指：

存在一个整数 i ii，使得 A AA 的前 i ii 个字母与 B BB 的前 i ii 个字母相同，且 A AA 的第 i + 1 i+1i+1 个字母小于 B BB 的第 i + 1 i+1i+1 个字母

如果 A AA 不存在第 i + 1 i + 1i+1 个字母且 B BB 存在第 i + 1 i + 1i+1 个字母，也视为 A AA 的第 i + 1 i + 1i+1 个字母小于 B BB 的第 i + 1 i + 1i+1 个字母

作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。

如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。

如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。

如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

输入格式

输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

输出格式

按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。

样例输入

WoAiLanQiaoBei

样例输出

AiLanQiao

数据范围

对于 20% 的评测数据，输入的总长度不超过 20 2020 个字母。

对于 50% 的评测数据，输入的总长度不超过 300 300300 个字母。

对于 70% 的评测数据，输入的总长度不超过 10000 1000010000 个字母。

对于所有评测数据，每个名字的长度不超过 10 1010 个字母，输入的总长度不超过 1000000 10000001000000 个字母。