Shortest Palindrome Construction

Given a string s of lowercase letters, your task is to find and output the shortest palindrome that can be formed by adding characters in front of s. In other words, you need to add the minimum number of characters to the beginning of s so that the resulting string is a palindrome.

This problem can be approached efficiently using the Knuth-Morris-Pratt (KMP) algorithm. The key idea is to create a temporary string as follows:

$temp = s + \# + reverse(s)$

Then, by computing the longest proper prefix which is also a suffix (LPS) array for temp, you can determine the minimum characters to add. More formally, if l is the length of the longest palindromic prefix (obtained from the LPS array), you should add the reverse of the remainder of the string. Formally, if s is of length n, the answer is given by:

$\text{answer} = reverse(s[l:n]) + s$

where l is lps[-1] in the KMP process. Your program should read input from stdin and write the result to stdout.

inputFormat

The input contains a single line consisting of the string s.

Constraints: s consists of only lowercase English letters and its length is at least 1.

outputFormat

Output the shortest palindrome obtained by adding characters only at the beginning of s.

## sample

aacecaaa

aaacecaaa