Next Greater Perfect String

A string is perfect if no two adjacent characters are the same. Given a string s of lowercase English letters (s itself may or may not be perfect), find the smallest perfect string that has the same length as s and is lexicographically strictly greater than s. If none exists, output -1.

输入格式

One line containing the string s. 1≤length of s≤200000, lowercase English letters only.

输出格式

Output the answer string; if none exists, output -1.

样例 1

输入：

abzzzcd

输出：

acababa

样例 2

输入：

zzab

输出：

-1

样例 3

输入：

abab

输出：

abac

样例说明

Example 1: s="abzzzcd". The z right after the prefix abz equals it, so the string must increase at an index ≤2; the z at index 2 cannot increase any further, so change the b at index 1 to c and fill the rest with the smallest alternating string ababa, giving "acababa". Example 2: s="zzab". The z at index 0 cannot increase, and increasing index 1 would also require going past z, so no answer exists; output -1. Example 3: s="abab" is already perfect, and the smallest perfect string strictly greater than it is "abac".