Вам задана строка \(s\), состоящая из строчных букв латинского алфавита. Пока в строке \(s\) есть хотя бы один символ, повторяющийся хотя бы дважды, вы выполняете следующую операцию:
- вы выбираете индекс \(i\) (\(1 \le i \le |s|\)), такой что символ на позиции \(i\) встречается хотя бы два раза в строке \(s\), и удаляете символ на позиции \(i\), то есть заменяете \(s\) на \(s_1 s_2 \ldots s_{i-1} s_{i+1} s_{i+2} \ldots s_n\).
Например, если \(s=\)«codeforces», то вы можете применить следующую последовательность операций:
- \(i=6 \Rightarrow s=\)«codefrces»;
- \(i=1 \Rightarrow s=\)«odefrces»;
- \(i=7 \Rightarrow s=\)«odefrcs»;
По заданной строке \(s\) найдите лексикографически максимальную строку, которая может быть получена после применения некоторой последовательности операций, оставляющей в строке только уникальные символы.
Строка \(a\) длины \(n\) лексикографически меньше строки \(b\) длины \(m\), если:
- существует индекс \(i\) (\(1 \le i \le \min(n, m)\)), такой что первые \(i-1\) символов у строк \(a\) и \(b\) совпадают, а \(i\)-й символ строки \(a\) меньше, чем \(i\)-й символ строки \(b\);
- или первые \(\min(n, m)\) символов у строк \(a\) и \(b\) совпадают и \(n < m\).
Например строка \(a=\)«aezakmi» лексикографически меньше строки \(b=\)«aezus».
Выходные данные
Для каждого набора входных данных выведите лексикографически максимальную строку, которая может быть получена после применения некоторой последовательности операций, оставляющей в строке только уникальные символы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz
|
odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz
|