Yaqi the squirrel is a bit clumsy. After losing in various games, he decided to play a matching game to soothe his wounded heart.

Yaqi's matching game is based on a string $S$ of length $n$, consisting only of lowercase English letters. Unlike traditional "match-3" rules, Yaqi needs to define a string $T$ of length $3$ as the matching criterion, and then the automatic matching process is handed over to the system: the system will find the leftmost occurrence of $T$ as a substring in the current $S$ and remove it from $S$, repeating this process until $T$ no longer exists as a substring in $S$.

The more times the matching occurs, the higher the score. Yaqi naturally wants a higher score, so he asks you to specify what string $T$ should be to maximize the number of automatic matches. If there are multiple such strings $T$, he hopes you will choose the one that is lexicographically smallest.

Recall: To determine the lexicographical relationship between two different strings of the same length, compare them character by character from left to right. The string with the smaller character at the first position where they differ is lexicographically smaller.

Input

The first line contains an integer $n$ ($3 \le n \le 10^6$), representing the length of the string $S$.

The second line contains the string $S$, which is guaranteed to consist only of lowercase English letters and has length $n$.

Output

The first line outputs an integer, the maximum number of automatic matches.

The second line outputs the lexicographically smallest string $T$ that achieves this maximum number of matches.

Examples

Input 1

10
aaababbaab

Output 1

3
aab

Input 2

14
liaoningdalian

Output 2

2
lia

Note

In the first example, the matching process is: aaababbaab $\to$ aabbaab $\to$ baab $\to$ b.

In the second example, the matching process is: liaoningdalian $\to$ oningdalian $\to$ oningdan.