# Maximize the Remaining String Solution Codeforces Round #710 Div. 3

You are given a string ss, consisting of lowercase Latin letters. While there is at least one character in the string ss that is repeated at least twice, you perform the following operation:

• you choose the index ii (1≤i≤|s|1≤i≤|s|) such that the character at position ii occurs at least two times in the string ss, and delete the character at position ii, that is, replace ss with s1s2…si−1si+1si+2…sns1s2…si−1si+1si+2…sn.

For example, if s=s=”codeforces”, then you can apply the following sequence of operations:

• i=6⇒s=i=6⇒s=”codefrces”;
• i=1⇒s=i=1⇒s=”odefrces”;
• i=7⇒s=i=7⇒s=”odefrcs”;

Given a given string ss, find the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.

A string aa of length nn is lexicographically less than a string bb of length mm, if:

• there is an index ii (1≤i≤min(n,m)1≤i≤min(n,m)) such that the first i−1i−1 characters of the strings aa and bb are the same, and the ii-th character of the string aa is less than ii-th character of string bb;
• or the first min(n,m)min(n,m) characters in the strings aa and bb are the same and n<mn<m.

For example, the string a=a=”aezakmi” is lexicographically less than the string b=b=”aezus”.Input

The first line contains one integer tt (1≤t≤1041≤t≤104). Then tt test cases follow.

Each test case is characterized by a string ss, consisting of lowercase Latin letters (1≤|s|≤2⋅1051≤|s|≤2⋅105).

It is guaranteed that the sum of the lengths of the strings in all test cases does not exceed 2⋅1052⋅105.Output

For each test case, output the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.

Example

Input

```6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz
```

Output

```odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz```

Solution :

#include <iostream>

#include <algorithm>

#include <cmath>

#include <string>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

#define rd(a) for(auto &i : a) cin >> i;

#define ct(a) for(auto i : a) cout << i << ‘ ‘;

#define ctp(a) for(auto i : a) cout << i << ‘\n’;

#define all(a) a.begin(), a.end()

#define int long long

signed main() {

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

int t;

cin >> t;

while (t–) {

string s, res = “”;

cin >> s;

int idx = 0;

set <char> used;

while (true) {

char symb = ‘0’;

for (int i = 25; i >= 0; i–) {

if (used.count(‘a’ + i))

continue;

int mi = 1e9;

for (int j = s.size() – 1; j >= idx; j–) {

if (s[j] == ‘a’ + i)

mi = j;

}

if (mi == 1e9)

continue;

map <char, int> left, right;

for (int i = idx; i < s.size(); i++) {

if (!used.count(s[i]) && i < mi)

left[s[i]]++;

if (!used.count(s[i]) && i > mi)

right[s[i]]++;

}

bool istrue = true;

for (auto i : left) {

if (right[i.first] == 0 && i.first != s[mi]) {

istrue = false;

}

}

if (istrue) {

symb = ‘a’ + i;

idx = mi + 1;

break;

}

}

if (symb == ‘0’)

break;

res = res + symb;

used.insert(symb);

}

cout << res << ‘\n’;

}

}