数奇な運命とともに、Nadeko は英小文字からなる文字列 $s$ を持っています。彼女の究極の願いは、以下の条件を満たす文字列 $t$ を構築することです:
- $t$ は $s$ を部分列として含まない。
- $s$ と一致しない $s$ のすべての部分列は、$t$ に部分列として含まれる。
可能な限り長さが最小となる文字列 $t$ を見つけるのを手伝ってください。そのような文字列が複数存在する場合は、どれを出力しても構いません。
入力
入力の唯一の行には、Nadeko の文字列 $s$($2 \le |s| \le 10^6$)が与えられます。$s$ は英小文字のみからなることが保証されます。
出力
問題の条件を満たす最小の長さの文字列 $t$ を $1$ 行に出力してください。
入出力例
入力 1
aaaa
出力 1
aaa
入力 2
bba
出力 2
bab
注記
2 番目の例では、文字列 bab は部分列として bb、ba、a、b を含みますが、bba は含みません。また、長さ $2$ の正しい文字列を構築することが不可能なのは明らかであるため、bab は正しい答えの一つです。