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