|
Темы:
Linear search
Vasya and Petya are playing the following game. They took a certain sequence of characters and then get new sequences from it, discarding the first few characters of the original sequence (it is allowed, among other things, not to discard a single character, but it is not allowed to discard all characters at once). Everyone names one such sequence. The winner is the one whose sequence comes first in alphabetical order.
Recall that if we compare two sequences, and their first K characters are the same, but the (K + 1)-th characters are different, then the one in which the (K + 1)-th character comes earlier in the alphabet will go alphabetically . If one sequence is the beginning of another, then the shorter one goes alphabetically first.
Write a program that will use the given sequence to determine what Vasya should be called so as not to lose to Petya.
Input
The first line of the input file contains the number N — the length of the original sequence (1≤N≤1000). The second line contains the sequence itself. The sequence consists only of capital Latin letters.
Imprint
Output the winning sequence to the output file.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
MAMA |
A |
Lines MAMA, AMA, MA, A are considered. Winning line A |
| 2 |
4
ALLO |
ALLO |
The original string is the winning one |
| 3 |
5
BBABB |
ABB |
|
|