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.

给你一个由英文字母小写组成的字符串 $s$。你需要对 $s$ 执行以下算法：

• 设 $x$ 为 $s$ 的最长前缀的长度，该前缀在 $s$ 中某处（作为连续子串）至少另出现一次（另一处出现的位置可以与该前缀重叠）。若 $x = 0$，则终止算法；否则，从 $s$ 中删除最前面的 $x$ 个字符，并重复执行。

前缀是指由给定字符串的若干个开头字母按原序组成的字符串（不允许重新排序）。空字符串也是一个合法的前缀。例如，字符串 "abcd" 共有 5 个前缀：空字符串、"a"、"ab"、"abc" 和 "abcd"。

例如，对 $s =$ "abcabdc" 执行该算法：

• 初始时，"ab" 是 $s$ 的最长前缀，且在 $s$ 中某处（作为连续子串）另出现（如位置 3–4），因此执行 1 次操作后 $s =$ "cabdc"。
• 接着，"c" 是当前 $s$ 的最长前缀，且在 $s$ 中某处另出现（如位置 2），因此执行 2 次操作后 $s =$ "abdc"。
• 此时 $x = 0$（因为 "abdc" 的所有非空前缀均未在 $s$ 中其他位置作为连续子串出现），算法终止。

求执行该算法后字符串的最终状态。

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来是 $t$ 行，每行描述一个测试用例。每行包含一个字符串 $s$。给定的字符串仅由英文字母的小写字母组成，且长度在 $1$ 到 $2 \cdot 10^5$（含）之间。

保证所有测试用例中字符串 $s$ 的长度总和不超过 $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.

对于每个测试用例，输出执行该算法后得到的字符串 $s$。可以证明，这样的字符串非空。

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

第一个测试用例已在题目描述中说明。

第二个测试用例中，无法对字符串 $s$ 执行任何操作。

第三个测试用例中：

• 初始时，$s =$ "bbbbbbbbbb"。
• 经过 $1$ 次操作后，$s =$ "b"。

第四个测试用例中：

• 初始时，$s =$ "codeforces"。
• 经过 $1$ 次操作后，$s =$ "odeforces"。
• 经过 $2$ 次操作后，$s =$ "deforces"。