CF1654B Prefix Removals

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.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — 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 \cdot 10^5 $ inclusive. It is guaranteed that the sum of the lengths of $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

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.

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".