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

Это усложненная версия этой задачи. Различия в ограничениях на сумму длин строк и на количество тестовых случаев. Вы можете делать взломы, только если обе версии этой задачи решены.

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

  • Длина строки $$$t$$$ не превосходит длину строки $$$s$$$.
  • $$$t$$$ является палиндромом, то есть она равна себе перевернутой.
  • Существует две строки $$$a$$$ и $$$b$$$ (возможно пустые), такие что $$$t = a + b$$$ (здесь операция «$$$+$$$» это конкатенация строк) и $$$a$$$ является префиксом строки $$$s$$$ и $$$b$$$ является суффиксом строки $$$s$$$.
Входные данные

Входные данные содержат несколько тестовых случаев. В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество тестовых случаев. Следующие $$$t$$$ строк описывают тестовые случаи.

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

Гарантируется, что сумма длин строк по всем тестовым случаям не превосходит $$$10^6$$$.

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

Для каждого тестового случая выведите строку максимальной длины, которая удовлетворяет описанным условиям. Если существует несколько решений, вы можете вывести любое.

Пример
Входные данные
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba
Выходные данные
a
abcdfdcba
xyzyx
c
abba
Примечание

В первом тестовом случае, вся строка $$$s = $$$«a» удовлетворяет всем условиям.

Во втором тестовом случае, строка «abcdfdcba» удовлетворяет всем условиям, потому что:

  • ее длина равна $$$9$$$, что не превосходит длину строки $$$s$$$, которая равна $$$11$$$;
  • она палиндром;
  • «abcdfdcba» $$$=$$$ «abcdfdc» $$$+$$$ «ba», где строка «abcdfdc» является префиксом строки $$$s$$$ и строка «ba» является суффиксом строки $$$s$$$.

Можно доказать, что невозможно найти более длинную такую строку.

В четвертом тестовом случае, строка «c» это правильный ответ, потому что «c» $$$=$$$ «c» $$$+$$$ «» и это допустимо, потому что по условию строки $$$a$$$ и $$$b$$$ могут быть пустыми. Другой возможный ответ на этот тест это строка «s».