Igor Perić

B. Prefix Removals

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a string s consisting of lowercase letters of the English alphabet. You must perform the following algorithm on s:

• Let x be the length of the longest prefix of s which occurs somewhere else in s as a contiguous substring (the other occurrence may also intersect the prefix). If x=0, break. Otherwise, remove the first x characters of s, and repeat.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string “abcd” has 5 prefixes: empty string, “a”, “ab”, “abc” and “abcd”.

For instance, if we perform the algorithm on s= “abcabdc”,

• Initially, “ab” is the longest prefix that also appears somewhere else as a substring in s, so s= “cabdc” after 1 operation.
• Then, “c” is the longest prefix that also appears somewhere else as a substring in s, so s= “abdc” after 2 operations.
• Now x=0 (because there are no non-empty prefixes of “abdc” that also appear somewhere else as a substring in s), so the algorithm terminates.

Find the final state of the string after performing the algorithm.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

This is followed by t lines, each containing a description of one test case. Each line contains a string s. The given strings consist only of lowercase letters of the English alphabet and have lengths between 1 and 2⋅105 inclusive.

It is guaranteed that the sum of the lengths of s over all test cases does not exceed 2⋅105.

Output

For each test case, print a single line containing the string s after executing the algorithm. It can be shown that such string is non-empty.

Example input

6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw

Example output

abdc
a
b
deforces
cf
xyzzw

Note

The first test case is explained in the statement.

In the second test case, no operations can be performed on s.

In the third test case,

• Initially, s= “bbbbbbbbbb”.
• After 1 operation, s= “b”.

In the fourth test case,

• Initially, s= “codeforces”.
• After 1 operation, s= “odeforces”.
• After 2 operations, s= “deforces”.

Solution

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        string a;
        cin >> a;
        int n = a.size();
        map<char, int> d;
        // store the index of last appearance of a[i]
        for (int i=0;i<n;i++) {
            d[ a[i] ] = i;
        }
        int i;
        for (i=0;i<n;i++) {
            // stop when there's no a[i] after index i
            if (d[ a[i] ] <= i) break;
        }
        // print the rest of the string from that position
        for (;i<n;i++) {
            cout << a[i];
        }
        cout << endl;
    }
    return 0;
}