Background

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".

Format

Input

Output

Samples

abXYab

"ab"

xx

"x"

xxx

"x"

Limitation

1s, 1024KiB for each test case.