Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap. Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is ""
Input Format
A string S.
Output Format
Print a string which is longest duplicate substring (any). If no duplicate substring is found just print "" (Without quotes)
Constraints
2 <= s.length <= 3 * 10^4 s consists of lowercase English letters
Example
Input
banana
Output
ana