Practice Strings and Palindrome with the exercise "Longest Palindrome"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Strings
Palindrome

Statement

Goal

A palindrome is a sequence of letters which reads the same backward as forward, like “madam” for example.

For a given input string S, you have to return the longest palindrome found within. If multiple substrings qualify, print them all in the same order as they appear in S.

Input

Line 1: A string S (only alphanumeric)

Output

N lines: Every longest palindrome contained in S

Constraints

0 < length of S < 10000

Example

Input

madam

Output

madam

Solve it

A higher resolution is required to access the IDE