Constructing a Minimal Palindrome

You are given a string s. Your task is to construct a palindrome by appending the minimum number of characters to the end of s (possibly none). A palindrome is a string that reads the same backward as forward.

For example, if s = "abc", appending "ba" results in "abcba". If s is already a palindrome (e.g. "aba"), return it unchanged.

If there exist multiple valid answers, any one will be accepted. The expected solution should work efficiently for strings of moderate length.

Hint: Find the longest suffix of s that is a palindrome, then append the reverse of the remaining prefix to the end of s.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Print a single line containing the palindrome obtained by appending the minimum number of characters to the end of s.## sample

abc

abcba