Shortest Palindrome

Given a string s, find and return the shortest palindrome you can obtain by adding characters in front of it. A palindrome is a string that reads the same forwards and backwards. In this problem, you are required to prepend the minimum number of characters to the original string to obtain a palindrome. The intended solution uses a KMP-based algorithm to compute the longest prefix which is also a suffix, achieving an overall linear time complexity.

inputFormat

A single line containing the string s. The input is read from standard input.

outputFormat

A single line containing the shortest palindrome formed by adding characters in front of s. The output is printed to standard output.## sample

aacecaaa

aaacecaaa