Contest Duration: - (local time) (150 minutes) Back to Home
A - Diverse Word /

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

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

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

### 制約

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

S

atcoder

### 出力例 1

atcoderb

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

abc

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.

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.

abc

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