A - Diverse Word Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 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 と出力せよ。

入力例 1

atcoder

出力例 1

atcoderb

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

入力例 2

abc

出力例 2

abcd

入力例 3

zyxwvutsrqponmlkjihgfedcba

出力例 3

-1

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

入力例 4

abcdefghijklmnopqrstuvwzyx

出力例 4

abcdefghijklmnopqrstuvx

Score : 300 points

Problem Statement

Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible diverse words in lexicographical order.

A word is called diverse if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, atcoder, zscoder and agc are diverse words while gotou and connect aren't diverse words.

Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

  • 1 \leq |S| \leq 26
  • S is a diverse word.

Input

Input is given from Standard Input in the following format:

S

Output

Print the next word that appears after S in the dictionary, or -1 if it doesn't exist.

Sample Input 1

atcoder

Sample Output 1

atcoderb

atcoderb is the lexicographically smallest diverse word that is lexicographically larger than atcoder. Note that atcoderb is lexicographically smaller than b.

Sample Input 2

abc

Sample Output 2

abcd

Sample Input 3

zyxwvutsrqponmlkjihgfedcba

Sample Output 3

-1

This is the lexicographically largest diverse word, so the answer is -1.

Sample Input 4

abcdefghijklmnopqrstuvwzyx

Sample Output 4

abcdefghijklmnopqrstuvx