Shortest Palindrome

hard

Unknown

Question Solve Solutions

1. You are given string(str). 
2. You can convert the given string to a palindrome by adding some characters in front of it.
3. You have to find the shortest palindromic string formed after performing the above-mentioned transformation.

Input Format

A string

Output Format

A string

Constraints

1 &lt;= length of the string &lt;= 10^4

Example

Input

coding

Output

gnidocoding

Subdomain Visit Count

Related Questions

easy Is Prime easy Prime Till N easy Reverse Integer easy GCD easy Fibonacci easy Fib Till N easy Exit Point of a matrix easy Placing N Queen in a matrix easy Arranging Vowels And Consonants easy Addition Of Two Linked List easy Circular Linked List easy Sort The Absolute List easy Decimal Number From Binary Linked List easy Find the largest rectangle in a matrix easy Count Pairs Having Sum X easy Delete alternate nodes of linked list