Given a string s, return the longest substring of s that is a palindrome.

A palindrome is a string that reads the same forward and backward.

If there are multiple palindromic substrings that have the same length, return any one of them.

Examples

Example 1

Input:  s = "ababd"
Output: "bab" (or "aba")

Both "aba" and "bab" are valid answers.

Example 2

Input:  s = "abbc"
Output: "bb"

Example 3

Input:  s = "a"
Output: "a"

Constraints

• 1 <= s.length <= 1000
• s consists of only digits and English letters

How the tests work: several substrings can tie for longest, so any valid one is accepted — a palindrome that occurs in s is compared by its length.