Find Lexicographically Smallest String

Given a lowercase string, find the smallest string of the same length that is lexicographically strictly greater and has no two equal adjacent characters. The original string may already contain adjacent repeats. If no such string exists, output -1.

输入格式

One line with a non-empty lowercase string. This site sets the length to 1..100000.

输出格式

Output the target string; if there is no solution, output -1.

样例 1

输入：

abbcd

输出：

abcab

样例 2

输入：

az

输出：

ba

样例 3

输入：

zz

输出：

-1

样例说明

Example 1: keep the prefix ab, raise the third character b to c, and fill with ab, giving abcab. Example 2: the second character z cannot be raised, so raise the first character a to b and fill with a, giving ba. Example 3: zz is already the largest string of length 2, so there is no solution: -1.