题目描述

Gotou 刚刚收到了一本字典。然而，他不认识字典中使用的语言。他对字典进行了一些分析，并意识到该字典包含了按词典顺序排列的所有可能的多样化单词。

如果一个单词是多样化的，那么它只包含非空的英文小写字母字符串，并且单词中的所有字母都不相同。例如，atcoder、zscoder 和 agc 是多样化的单词，而 gotou 和 connect 不是多样化的单词。

给定一个多样化的单词 $S$，找出字典中按字典顺序排列的下一个单词，即按字典顺序排列的最小的比 $S$ 大的多样化单词。如果不存在这样的单词，则确定不存在。

如果 $X = x_{1}x_{2}...x_{n}$ 和 $Y = y_{1}y_{2}...y_{m}$ 是两个不同的字符串，则 $X$ 按字典顺序排列在 $Y$ 之后当且仅当 $Y$ 是 $X$ 的前缀，或者存在最小整数 $j$，使得 $x_{j} \\neq y_{j}$ 且 $x_{j} > y_{j}$。

约束条件

• $1 \\leq |S| \\leq 26$
• $S$ 是一个多样化的单词。

输入

从标准输入读入输入数据，格式如下：

$S$

输出

打印出字典中按字典顺序排列的在 $S$ 之后的下一个单词，如果不存在，则输出-1。

示例输入 1

atcoder

示例输出 1

atcoderb

atcoderb 是按字典顺序排列的在 atcoder 之后最小的多样化单词。注意，atcoderb 在字典中按字典顺序比 b 靠前。

示例输入 2

abc

示例输出 2

abcd

示例输入 3

zyxwvutsrqponmlkjihgfedcba

示例输出 3

-1

这是字典中按字典顺序排列的最大的多样化单词，因此答案为 -1。

示例输入 4

abcdefghijklmnopqrstuvwzyx

示例输出 4

abcdefghijklmnopqrstuvx