Shortest Palindrome

You are allowed to add characters to the front of a string, and only to the front. Write shortest_palindrome(s) that returns the shortest palindrome you can make this way.

Examples

shortest_palindrome("racecars")  # returns 'sracecars'
shortest_palindrome("abcd")      # returns 'dcbabcd'
shortest_palindrome("level")     # returns 'level'

"racecars" already starts with the palindrome "racecar", so only the final "s" needs a mirror image at the front. "level" is a palindrome already, so nothing is added.

Constraints

• s has 0 to 20,000 lowercase letters.