伴随着扭曲的命运，Nadeko 有一个由小写字母组成的字符串 $s$。她最终的愿望是构造一个字符串 $t$，使得以下条件成立：
- $t$ 不包含 $s$ 作为子序列。
- $s$ 的每一个不与 $s$ 本身完全相同的子序列，都作为子序列包含在 $t$ 中。
帮助她找到一个长度尽可能短的字符串 $t$。如果存在多个这样的字符串，你可以输出其中任意一个。
输入格式
输入只有一行，包含一个字符串 $s$（$2 \le |s| \le 10^6$）——即 Nadeko 的字符串。保证 $s$ 仅包含小写字母。
输出格式
输出单行，包含满足题目条件的、长度最短的任意字符串 $t$。
样例
输入样例 1
aaaa
输出样例 1
aaa
输入样例 2
bba
输出样例 2
bab
说明
在第二个样例中，字符串 "bab" 包含 "bb"、"ba"、"a"、"b" 作为子序列，但不包含 "bba"。同样显而易见的是，无法构造出一个长度为 $2$ 且满足条件的序列，因此 "bab" 是一个可能的答案。