No submission language available for this problem.

Background

Special for beginners, ^_^

Description

蓝星非常热闹，有各个星球的游客来蓝星游玩。时空管理局小 A 被临时任命为蓝星的港口的管理员。

为了更好的管理人流，蓝星要求所有的各个星球的游客都需要提前预约，系统上所有预约游客的名字，小 A 都能看到。每个游客的名字由一个大写英文字母开始，后面跟 0 个或多个小写英文字母。（游客可能重名）

小 A 特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。

一个名字 A 小于另一个名字 B 是指：存在一个整数 i，使得 A 的前 i 个字母与 B 的前 i 个字母相同，且 A 的第 i + 1 个字母小于 B 的第 i + 1个字母。（如果 A 不存在第 i+1 个字母且 B 存在第 i+1 个字母，也视为 A 的第 i+1 个字母小于 B 的第 i + 1个字母）

作为小 A 的助手，需要你按照小 A 的想法安排游客，同时你又希望上午有尽量多的游客游玩。

请告诉小 A 让哪些游客上午游玩。

如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

Format

Input

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

Output

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

Samples

WoAiShiKongGuanLiJu

AiGuanJu

Limitation

每个名字的长度不超过 10 个字母，输入的总长度不超过10000

1s, 1024KiB for each test case.