409048: GYM103427 G Encoded Strings II

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Encoded Strings IItime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Tommy has just invented an interesting string encoding algorithm, which is described below.

  • For every string $$$S$$$, we may define a character-mapping function $$$F_S$$$, which maps every character occurring in $$$S$$$ to a lowercase letter, as below $$$$$$ F_S(c) = \operatorname{chr}(G(c, S)) $$$$$$ where $$$\operatorname{chr}(i)$$$ is the $$$(i+1)$$$-th lowercase Latin letter, and $$$G(c, S)$$$ is the number of different characters after the last occurrence of $$$c$$$ in $$$S$$$.
  • To encode a string $$$S$$$ by Tommy's algorithm, replace every character $$$c$$$ in $$$S$$$ by $$$F_S(c)$$$ simultaneously.

For example, the encoded string of abc is cba, and the encoded string of cac is aba.

You are given a string of length $$$n$$$ and then encode all the $$$2^n-1$$$ nonempty subsequences. Your task is to find the encoded string that has the greatest lexicographical order among all the encoded strings.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 1\,000)$$$.

The second line contains a string of length $$$n$$$, which consists of only the first $$$20$$$ lowercase letters, a to t.

Output

Output the encoded string that has the greatest lexicographical order among all the encoded strings.

ExamplesInput
4
aacc
Output
bbaa
Input
4
acac
Output
bba

加入题单

上一题 下一题 算法标签: