B. Префиксные удаления
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$, состоящая из строчных букв латинского алфавита. Вы должны выполнить над строкой $$$s$$$ следующий алгоритм:

  • Обозначим за $$$x$$$ длину наибольшего префикса $$$s$$$, который встречается где-то еще в $$$s$$$ как подстрока из последовательных символов (это вхождение может пересекаться с самим префиксом). Если $$$x = 0$$$, закончите алгоритм. Иначе удалите первые $$$x$$$ символов $$$s$$$ и повторите.

Префиксом строки называются несколько первых букв данной строки без изменения порядка. Пустая строка тоже является корректным префиксом. Например, у строки «abcd» пять префиксов: пустая строка, «a», «ab», «abc» и «abcd».

Например, выполним алгоритм над $$$s =$$$ «abcabdc».

  • Изначально «ab» является самым длинным префиксом, который встречается где-то еще в $$$s$$$ как подстрока, поэтому после $$$1$$$ операции $$$s =$$$ «cabdc».
  • Затем «c» является самым длинным префиксом, который встречается где-то еще в $$$s$$$, поэтому после $$$2$$$ операций $$$s =$$$ «abdc».
  • После этого $$$x=0$$$ (т. к. нет префиксов «abdc», которые встречаются как подстрока где-либо еще в $$$s$$$), поэтому алгоритм завершается.

Найдите финальное состояние строки после завершения алгоритма.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют $$$t$$$ строк, каждая из который описывает один набор входных данных. Каждая строка содержит строку $$$s$$$. Данная строка содержит только строчные буквы латинского алфавита и имеет длину от $$$1$$$ до $$$2 \cdot 10^5$$$ включительно.

Гарантируется, что сумма длин $$$s$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите строку $$$s$$$ после завершения алгоритма. Можно показать, что эта строка не может быть пустой.

Пример
Входные данные
6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw
Выходные данные
abdc
a
b
deforces
cf
xyzzw
Примечание

Первый пример пояснен в условии задачи.

Во втором примере нельзя сделать ни одной операции с $$$s$$$.

В третьем примере,

  • Изначально $$$s =$$$ «bbbbbbbbbb».
  • После $$$1$$$ операции $$$s =$$$ «b».

В четвертом примере,

  • Изначально $$$s =$$$ «codeforces».
  • После $$$1$$$ операции $$$s =$$$ «odeforces».
  • После $$$2$$$ операции $$$s =$$$ «deforces».