H. Hidden Textland Pattern
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the digital expanse of Textland, a land renowned for its affinity with strings and textual puzzles, a challenge has arisen that has piqued the curiosity of its inhabitants. The challenge involves a mystical string, said to hold secrets to the ancient algorithms of Textland. This string, composed of lowercase letters, is rumored to contain hidden patterns that repeat throughout its length. The quest is to uncover the most repeated substring within this enigmatic string. However, the challenge comes with a twist: if multiple substrings are equally repeated, the quest seeks the longest among them. Should a tie still persist, the preference shifts to the substring that is smallest lexicographically. The citizens of Textland are intrigued, for deciphering this puzzle would mean unlocking a piece of the lost lore of their digital realm.

Input

The adventure begins with two lines. The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the length of the mystical string $$$S$$$. The second line contains the string $$$S$$$, composed of lowercase English letters. This string, a relic from the ancient coders of Textland, is the key to the challenge.

Output

Reveal the most repeated substring according to the rules of the challenge. If the string is a unique sequence of characters with no repetitions, return the entire string itself as it stands as the only substring of its kind.

Examples
Input
3
acb
Output
acb
Input
8
abdabdab
Output
ab