配点 : $300$ 点

問題文

ゴトウは辞書をもらいました。ところが、その辞書は知らない言語で書かれていました。 分析した結果、その辞書にはありうるすべての 多彩 な単語が辞書順に載っていることがわかりました。

単語は、それが英小文字からなる空でない文字列であって、単語内の文字がすべて異なる場合、そしてその場合に限って 多彩 であると呼ばれます。例えば、atcoder、zscoder、agc は多彩な単語ですが、gotou、connect は多彩な単語ではありません。

多彩な単語 $S$ が与えられるので、この辞書で $S$ の次に載っている単語、すなわち、$S$ より辞書順で大きいような、辞書順で最小の多彩な単語を求めてください。あるいは、そのような単語は存在しないと判定してください。

なお、$X = x_{1}x_{2}...x_{n}$、$Y = y_{1}y_{2}...y_{m}$ を二つの異なる文字列とするとき、$Y$ が $X$ の接頭辞であるか、$j$ を $x_{j} \neq y_{j}$ であるような最小の整数として $x_{j} > y_{j}$ である場合、そしてその場合に限って $X$ は $Y$ より辞書順で大きいといいます。

制約

• $1 \leq |S| \leq 26$
• $S$ は多彩な単語である。

入力

入力は標準入力から以下の形式で与えられる。

$S$

出力

辞書で $S$ の次に載っている単語を出力せよ。ただし、そのような単語が存在しない場合は -1 と出力せよ。

atcoder

atcoderb

atcoder より辞書順で大きいような、辞書順で最小の多彩な単語は atcoderb です。atcoderb は b より辞書順で小さいことに注意してください。

abc

abcd

zyxwvutsrqponmlkjihgfedcba

-1

これが辞書順で最も大きい多彩な単語なので、答えは -1 です。

abcdefghijklmnopqrstuvwzyx

abcdefghijklmnopqrstuvx