Same Sequence

In Progress

Medium

Helpful

A competition is being organized at Peter's school. In that

competition, some balls are arranged in a sequence on a table. Every

ball has a specific color.

The goal is to add a minimum number of balls to the left side of the

sequence such that the sequence of colors of balls remains in the

same order when viewed from both the left and right sides.

Help Peter win this competition by determining the sequence of

colors of balls after adding the minimum number of balls on the left

side.

Given a string sequence that represents the sequence of colors

of the balls. The colors of different balls are represented by letters.

Write a program to print a sequence of colors of balls obtained by

adding a minimum number of balls to the left side of the given

sequence that will make Peter win the game.

Note

The colors of the balls are represented by letters.

Example: $r$ for red, $g$ for green, etc.

Input

The input will be a single line containing a string

sequence

representing the sequence of colors of the balls.