Shortest Palindrome

Given a string s, you are allowed to add characters in front of it to form a palindrome. Your task is to find and return the shortest palindrome that can be created by pre-pending characters to s.

For example, if s = "abcd", by pre-pending "dcb" you obtain "dcbabcd", which is a palindrome. More formally, if you let \(P\) be a palindrome and \(P = X + s\) (where + denotes string concatenation), find the palindrome \(P\) with the minimum possible length.

Note that a string is a palindrome if it reads the same forward and backward. In \(\LaTeX\) you can express this as: A string \(S\) is a palindrome if \(S = \text{reverse}(S)\).

inputFormat

The input is a single line containing a non-empty string s consisting of lowercase English letters.

outputFormat

Output the shortest palindrome that can be obtained by adding characters solely to the front of s. The output should be printed as a single line.

abcd

dcbabcd