Smallest Palindrome Extension

Given a string (S) consisting of lowercase English letters, your task is to append the minimal number of characters to the end of (S) so that the resulting string is a palindrome. A palindrome is a string that reads the same forwards and backwards. For example, if (S = \texttt{race}), then appending (\texttt{car}) yields (\texttt{racecar}). If the string is already a palindrome, no additional characters are required. Your solution should compute and output the smallest such palindrome extension.

inputFormat

The input consists of a single line containing the string (S). The string may be empty and contains only lowercase English letters.

outputFormat

Output a single line containing the smallest palindrome that can be obtained by appending characters to the end of (S).## sample

race

racecar