Shortest Palindrome Extension

You are given a string \( s \) consisting of lowercase letters. Your task is to form the shortest palindrome by appending characters to the end of \( s \). More formally, you need to find the shortest string \( t \) such that \( s + t \) is a palindrome. You are allowed to append characters only at the end of the string.

For example, given \( s = \texttt{race} \), by appending \( \texttt{car} \) we obtain \( \texttt{racecar} \), which is a palindrome.

Note: If \( s \) is already a palindrome, simply output \( s \) unchanged.

inputFormat

The input consists of a single line containing the string \( s \). The string may be empty and will consist only of lowercase English letters.

outputFormat

Output the shortest palindrome that can be obtained by appending characters to the end of \( s \).

race

racecar