Longest Repeated Substring Repeat

Given a string u consisting only of the characters a and b, find a contiguous substring of u that can be written as a concatenation of k copies of some non‐empty string t, i.e., s = t t ... t (k times). Such a string s is called a \( (k,l)\text{-repeat} \) string where \( l \) is the length of t and \( k \ge 1, l \ge 1 \).

For example, the string abaabaabaaba is a \( (4,3)\text{-repeat} \) string because it is formed by concatenating aba 4 times.

Your task is to extract one contiguous segment from u that is a \( (k,l)\text{-repeat} \) string such that the value of \( k \) is maximized. If there are multiple answers, you may output any one of them.

Note: Every non-empty substring is a valid \( (k,l)\text{-repeat} \) string with \( k = 1 \) (where \( t = s \)). Thus, you are guaranteed to have an answer, but you need to find one with the maximum repetition count \( k \).

inputFormat

The input consists of a single line containing the string u (only characters a and b).

outputFormat

Output a contiguous substring of u that is a \( (k,l)\text{-repeat} \) string with the maximum possible \( k \). If multiple answers exist, output any one.

sample

abaabaabaaba

abaabaabaaba