Given a strings, find the longest palindromic substring ins. You may assume that the maximum length of is 1000.

Example:

Input:
 "babad"


Output:
 "bab"


Note:
 "aba" is also a valid answer.

Example:

Input:
 "cbbd"


Output:
 "bb"

NOTES