伴隨住扭曲嘅命運,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 係一個可行嘅答案。