CF1326D2.Prefix-Suffix Palindrome (Hard version)

This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string $s$, consisting of lowercase English letters. Find the longest string, $t$, which satisfies the following conditions:

• The length of $t$ does not exceed the length of $s$.
• $t$ is a palindrome.
• There exists two strings $a$ and $b$ (possibly empty), such that $t = a + b$ ( "$+$" represents concatenation), and $a$ is prefix of $s$ while $b$ is suffix of $s$.

这是该问题的困难版本。区别在于字符串长度总和以及测试用例数量的约束条件。仅当您解决了该任务的所有版本后，才允许进行 hack。

给定一个由小写英文字母组成的字符串 $s$。请找出最长的字符串 $t$，使其满足以下条件：

• $t$ 的长度不超过 $s$ 的长度；
• $t$ 是一个回文串；
• 存在两个字符串 $a$ 和 $b$（可能为空），使得 $t = a + b$（其中 "$+$" 表示字符串连接），且 $a$ 是 $s$ 的前缀，$b$ 是 $s$ 的后缀。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. The next $t$ lines each describe a test case.

Each test case is a non-empty string $s$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^6$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来的 $t$ 行，每行描述一个测试用例。

每个测试用例是一个非空字符串 $s$，由小写英文字母组成。

保证所有测试用例中字符串长度之和不超过 $10^6$。

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

对于每个测试用例，输出满足上述条件的最长字符串。如果存在多个可能的解，输出其中任意一个即可。

In the first test, the string $s = $"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

• Its length is $9$, which does not exceed the length of the string $s$, which equals $11$.
• It is a palindrome.
• "abcdfdcba" $=$ "abcdfdc" $+$ "ba", and "abcdfdc" is a prefix of $s$ while "ba" is a suffix of $s$.

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $=$ "c" $+$ "" and $a$ or $b$ can be empty. The other possible solution for this test is "s".

在第一个测试中，字符串 $s = $"a" 满足所有条件。

在第二个测试中，字符串 "abcdfdcba" 满足所有条件，因为：

• 其长度为 $9$，未超过字符串 $s$ 的长度（$s$ 的长度为 $11$）。
• 它是一个回文串。
• "abcdfdcba" $=$ "abcdfdc" $+$ "ba"，其中 "abcdfdc" 是 $s$ 的一个前缀，而 "ba" 是 $s$ 的一个后缀。

可以证明：不存在更长的、满足所有条件的字符串。

在第四个测试中，字符串 "c" 是正确的，因为 "c" $=$ "c" $+$ ""，且 $a$ 或 $b$ 可以为空。该测试的另一个可能解是 "s"。