Longest Repeating Substring

Given a string \( s \) consisting solely of lowercase English letters, your task is to find the longest substring that appears at least twice in \( s \). Note that the repeating occurrences of the substring may overlap.

If there are multiple substrings of maximum length that repeat, you should return the substring that appears first in \( s \). If no such substring exists, output an empty string.

For example, if \( s = \texttt{banana} \), the answer is \( \texttt{ana} \) because "ana" is the longest substring that repeats.

inputFormat

The input is a single line containing a non-empty string \( s \) of lowercase English letters.

Constraints: \( 1 \leq |s| \leq 10^5 \).

outputFormat

Output the longest repeating substring in \( s \). If no repeating substring exists, output an empty string.

banana

ana