Shortest Palindrome Construction

Your task is to transform the given string into the shortest palindrome by adding a sequence of characters in front of it. More formally, given a string \( s \), you need to find the minimal string \( p \) such that \( p+s \) is a palindrome. This is equivalent to finding the shortest palindrome that can be formed by adding characters only at the beginning of \( s \).

For example, if \( s = \texttt{race} \), then the output should be \( \texttt{ecarace} \) since adding \( \texttt{eca} \) to the front of \( s \) results in a palindrome.

inputFormat

The input consists of a single line containing the string \( s \), where \( 0 \le |s| \le 10^5 \). The string may contain alphanumeric characters.

outputFormat

Output the shortest palindrome obtained by appending characters to the front of the input string.

race

ecarace