CF1326D2 Prefix-Suffix Palindrome (Hard version)

这是本题的困难版。 区别在于对字符串长度总和和多测数量的限制。 给你一个由小写英文字母组成的字符串 $s$。找出满足以下条件的最长字符串 $t$： - $t$ 的长度不超过 $s$ 的长度。 - $t$ 是一个回文字符串。 - 存在两个字符串 $a$ 和 $b$（可能为空，且 $a$ 和 $b$ 不相交），使得 $t=a+b$ （加号表示连接），并且 $a$ 是 $s$ 的前缀，$b$ 是 $s$ 的后缀。

输入由多个测试样例组成。第一行包含一个整数 $t$（ $1\le t\le 10^5$），即测试样例的数量。接下来的 $t$ 行分别描述一个测试样例。 每组数据的第一行都是一个非空字符串 $s$，且仅由小写英文字母组成。 保证所有测试样例的字符串长度之和不超过 $10^6$。

对于每个测试样例，打印满足上述条件的最长字符串。 如果存在多个可能的解决方案，则打印其中任何一个。

在第一个样例中，字符串 `a` 满足所有条件。 在第二个样例中，字符串 `abcdfdcba` 满足所有条件。 - 因为它的长度是 $9$，没有超过字符串 $s$ 的长度 $11$。 - 它是一个回文串。 - `abcdfdcba=abcdfdc+ba`，`abcdfdc` 是 $s$ 的前缀，而 `ba` 是 $s$ 的后缀。 可以证明，不存在满足条件的更长字符串。 在第四次样例中，字符串 `c` 是正确的，因为 `c=c +""(即空串)`，又因为 $a$ 或 $b$ 可以为空。 这个样例的另一个可能解法是 `s`。