You are given a string \(s\) consisting only of lowercase letters. A substring \([l;\ r]\) of \(s\) is a string \(s[l...r]\) and its length is equal to \(r-l+1\). Find the substring of \(s\) that contains a maximum number of occurrences.

If several answers exist, then print the one with the maximum length. If there are still several answers, then print the one with the minimum index of the first occurrence.

Input format

The single line contains string \(s\) (\(1 \le |s| \le 10^5\)).

Output format

Find the suitable substring.