Lexicographically Smallest Non-Palindromic String

You are given a lowercase alphabet string s that is a palindrome. Update one character such that s is no longer a palindrome and is lexicographically smallest.

Constraints

• 2 ≤ n ≤ 100,000 where n is the length of s

https://binarysearch.com/problems/Lexicographically-Smallest-Non-Palindromic-String

Examples

Example 1

Input

• s = racecar

Output

• answer = aacecar

Explanation

We can change the first "r" to "a" to get the lexicographically smallest string that is not a palindrome.

Solution