Given a string s, return the longest palindromic substring.

Example 1:

Input: babad
Output: bab

Example 2:

Input: cbbd
Output: bb

Constraints:

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

Input format: One line — the string.

Output format: Longest palindromic substring.