Contest: Task: Related: TaskB

Score : $300$ points

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}$.

- $1 \leq |S| \leq 26$
- $S$ is a diverse word.

Input is given from Standard Input in the following format:

$S$

Print the next word that appears after $S$ in the dictionary, or `-1`

if it doesn't exist.

atcoder

atcoderb

`atcoderb`

is the lexicographically smallest diverse word that is lexicographically larger than `atcoder`

. Note that `atcoderb`

is lexicographically smaller than `b`

.

abc

abcd

zyxwvutsrqponmlkjihgfedcba

-1

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

.

abcdefghijklmnopqrstuvwzyx

abcdefghijklmnopqrstuvx