You are given a string $s$ with length $n$ and your task is to find the longest repeating substring. A repeating substring of $s$ is a substring of $s$ such that it appears at least twice in $s$. The appearances of substrings can overlap.

Input

The first and only line of input contains string $s$ with $n$ characters between a-z. All letters are small case.

Output

Output the longest repeating substring.

If there are multiple equally long repeating substrings, you should print the lexicographically smallest such string.

Limits

• $1 \le n \le 10^5$

Example

Input:

abcdabcdabcd

Output:

abcdabcd