Longest Non-Overlapping Prefix Suffix

Problem Description

Given a string, return the longest substring that appears at both the beginning and end of the string without overlapping. For example, sameEnds("abXab") is "ab".

Input Format

The input is given from standard input in the following format.

s

Output Format

Output to standard output in the following format.

result

Sample

abXYab

"ab"

xx

"x"

xxx

"x"

Sample Explanation

For abXYab, "ab" is the longest substring that appears at both the beginning and end without overlapping. For xx, "x" is the longest substring that appears at both the beginning and end without overlapping. For xxx, "x" is the longest substring that appears at both the beginning and end without overlapping.

Constraints

The length of the string $s$ is between $1$ and $10^5$. The string $s$ consists of lowercase English letters.