题目描述

ゴトウ收到了一个字典。然而，这本字典是用他不认识的语言写的。经过分析，他发现这本字典中包含了所有可能的多彩单词，并且按照字典序排列。

如果一个单词是由小写英文字母组成的非空字符串，且单词中的每个字母都不相同，那么这个单词被称为多彩单词。例如，atcoder、zscoder、agc 是多彩单词，而 gotou、connect 不是多彩单词。

给定一个多彩单词 $S$，请你在这本字典中找出排在 $S$ 后面的单词中，字典序最小的多彩单词。或者，如果不存在这样的单词，请输出 -1。

另外，设 $X = x_1x_2...x_n$，$Y = y_1y_2...y_m$ 是两个不同的字符串。如果 $Y$ 是 $X$ 的前缀，或者存在最小的整数 $j$ 使得 $x_j \neq y_j$ 并且 $x_j > y_j$，那么 $X$ 被认为在字典序上大于 $Y$。

输入格式

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

$S$

输出格式

输出在字典中排在 $S$ 后面的字典序最小的多彩单词。如果不存在这样的单词，输出 -1。

样例 1

输入

atcoder

输出

atcoderb

样例 2

输入

abc

输出

abcd

样例 3

输入

zyxwvutsrqponmlkjihgfedcba

输出

-1

样例 4

输入

abcdefghijklmnopqrstuvwzyx

输出

abcdefghijklmnopqrstuvx

说明/提示

限制条件

• $1 \leq |S| \leq 26$
• $S$ 是多彩单词。

样例解释 1

字典序上大于 atcoder 的最小多彩单词是 atcoderb。注意，atcoderb 在字典序上比 b 小。

样例解释 3

这是字典序最大的多彩单词，因此答案是 -1。

由 ChatGPT 4.1 翻译