Quilindrome (Hard)

Apart from the input limits, the difficulty level makes no difference to this problem.

After a long think, Sangmin came up with a great nickname, "qilip". Oh, a palindrome!.. he thought, but...

For this nickname to be a palindrome, it would have to read "qilip" when read backward too. Read backward, it becomes "piliq", so the nickname is not a palindrome. A string that looks like a perfect mirror image around its center is called a "quilindrome". For example, "dad" is a palindrome but not a quilindrome, and "mom" is both. Everyone wants a quilindrome nickname.

Daeyoung: Sangmin, make my nickname a quilindrome too!

Sangmin: What's your nickname?

Daeyoung: dy2000

Sangmin: dY2000SYb

Daeyoung: !

Sangmin has been swamped with requests for great quilindrome nicknames, and it is making his daily life hard. A great quilindrome nickname is a palindrome that contains the original nickname as a substring. In other words, if you trim both ends of a great quilindrome nickname, you get the original nickname. Everyone is obsessed with quilindromes, so as long as a quilindrome can be made, changing letter case is fine. For example, "yoy" is not a quilindrome, but "YoY" with the capitals changed is, so people are happy with it.

Write a program that builds the shortest great quilindrome nickname for Sangmin. Special rule: a character that is its own mirror image may be placed at the center of an odd-length quilindrome.

The mirror table Sangmin made, which is not exact but "good enough", is below.

The first line contains the original nickname $S$.

Print the shortest great quilindrome nickname. If no great quilindrome nickname can be made, print "-1".

$|S| \le 1,000,000$