WordFlip

The game WordFlip has become all the rage recently. In this game each player is assigned a string of $N$ characters ($1 \le N \le 200,000$) which consists of the upper case letters A through Z, and each player can choose a Flip of their string to compete against the other players' strings.

A Flip of a string $T$ is achieved by taking some (possibly empty) prefix of the string and moving it to the end. In WordFlip a string beats another if it is lexicographically smaller. This means that it would appear earlier than the other string in a dictionary. As an example, all possible Flips of the string LAKE from strongest to weakest are AKEL, ELAK, KELA, LAKE.

Adrian has been assigned the string $S$ and wants to make the best Flip possible so that he can beat all his friends at WordFlip. To this end, Adrian has asked for your help to write a program to find the strongest possible Flip of his string.

Note: If you are receiving 'Time Limit Exceeded' with Python code, you should try submitting with language 'Python 3.6 (PyPy 7.3)' as this will generally make your code run faster, but it should be noted that this could possibly make your code run slower in some cases.

Input

The first line contains a single integer $N$.

The second line contains the string $S$ which has $N$ characters.

Output

On a single line output the strongest (lexicographically smallest) possible flip of $S$.

Subtasks

• Subtask 1 (28%): $N \le 1,000$
• Subtask 2 (32%): There is at most $1,000$ of each letter
• Subtask 3 (40%): No further constraints.