Search for the longest palindromic substring in a string

Java Medium strings

Task «Search for the longest palindromic substring in a string»

Given a string consisting of lowercase Latin letters. Find and output the longest subpalindrome (a substring that reads the same from left to right and from right to left). If there are several such substrings, output the first one in order. The length of the string does not exceed 1000 characters.

Input Format

The input is a single string S (1 ≤ |S| ≤ 1000), consisting of lowercase Latin letters.

Output Format

Output one desired subpalindrome.

Examples

Example 1

INPUT

babad

OUTPUT

bab

Example 2

INPUT

racecar

OUTPUT

racecar

Example 3

INPUT

a

OUTPUT

a

main.java