Get Special String

Output the smallest string that has the same length as s, is lexicographically strictly greater than s, and has no two equal adjacent characters; if none exists, output −1. The original string itself may already contain adjacent repeats, and z cannot wrap around to a.

输入格式

One line containing a lowercase string. 1≤length≤1000000.

输出格式

Output the target string, or −1 if none exists.

样例 1

输入：

abbd

输出：

abca

样例 2

输入：

abccde

输出：

abcdab

样例 3

输入：

zzab

输出：

-1

样例说明

The answers are abca, abcdab and −1. You cannot change only the last letter while keeping repeated characters inside the original string.