伴隨著扭曲的命運,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 是一個可能的答案。