Ciąg

Time limit1sMemory limit128 MB

Summary

Bajtek needs the shortest string over the given alphabet that is not a subsequence of the word, and the lexicographically smallest among shortest such strings.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, String, Prefix sum
Solved: No attempts yet

Problem

Bajtek got bored with Bajcraft and went looking for a new pastime. While browsing Bajternet he found a contest that pays out a lot of Bajtalars. In each round the organizers fix an alphabet and a word, and you win by submitting a string of minimal length, built from that alphabet, that is not a subsequence of the word. A subsequence of a word is any word obtained by deleting zero or more of its letters, keeping the remaining letters in their original order. Whoever submits such a shortest string first wins, and the prize is doubled for the string that is also the smallest in lexicographic (dictionary) order.

The rounds keep growing, so Bajtek asked you for a program. Given the alphabet and the word, find the shortest string over the alphabet that is not a subsequence of the word. If more than one shortest string exists, output the lexicographically smallest one.

Input

The first line contains two integers $a$ and $n$ ( $1 \le a \le 26$ , $1 \le n \le 1\,000\,000$ ): the alphabet size and the length of the word. An alphabet of size $a$ consists of the first $a$ lowercase letters of the English alphabet (for example, $a = 3$ gives the letters a, b, and c). The second line contains the word of length $n$ , made up only of letters from this alphabet.

Output

Print a single line with the required string, its letters written with no spaces between them.

Examples3

Example 1
Input
```
3 8
cbacbacb
```
Expected output
```
aaa
```
Example 2
Input
```
2 3
aab
```
Expected output
```
ba
```
Example 3
Input
```
2 1
b
```
Expected output
```
a
```