Shortest Palindrome

Given a string S consisting of uppercase and lowercase alphabetic characters, your task is to form the shortest palindrome by adding characters only to the front of S.

A palindrome is a string that reads the same backward as forward. For example, the string "racecar" is a palindrome, and "abcd" is not.

To solve this problem efficiently, you might consider using the KMP algorithm to compute the longest palindromic prefix. The constraints ensure that the length of S is between \(1\) and \(10^5\). If needed, you can assume that the input will conform to these constraints.

Examples:

• Input: aacecaaa — Output: aaacecaaa
• Input: abcd — Output: dcbabcd
• Input: racecar — Output: racecar

inputFormat

The input consists of a single line containing the string S, where 1 ≤ |S| ≤ 10^5. The string S contains only uppercase and lowercase English letters.

outputFormat

Print the shortest palindrome that can be formed by adding characters in front of S.## sample

aacecaaa

aaacecaaa