Minimum MAW

A contiguous substring of a string $S$ is a sequence of characters of length zero or more removed from the beginning and the end of $S$, respectively (except for all the characters of $S$ that have been removed). For example, the string abc has six consecutive substrings: a, ab, abc, b, bc, c.

Given a string $S$ and $T$, if $T$ satisfies the following conditions, then $T$ is said to be a minimal absent word (hereafter written as MAW) of $S$.

• $T$ is at least two in length.
• $T$ is not a continuous substring of $S$.
• Any continuous substring of $T$ that is not a $T$ is a continuous substring of $S$.

For example, if the string $S$ is aabb, then the MAW of $S$ is the string aaa, ba, bbb.

The string is given. Write a program to find the smallest string in the MAW of that string in lexicographic order (the order in which words are arranged in an English-Japanese dictionary).

Input

The input is given in the following form.

$N$
$str$

The first line is the length of the string $N$ ($3 \leq N \leq 400,000$), and the second line is a string of length $N$ consisting of lowercase letters.

Output

Output the smallest MAW in lexical order in a line.

Sample Input and Output

Sample Input 1

4
aabb

Sample Output 1

aaa

Sample Input 2

4
tree

Sample Output 2

eee

 

---