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 ss, consisting of lowercase English letters. Find the longest string, tt, which satisfies the following conditions:

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

Input

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1051≤t≤105), the number of test cases. The next tt lines each describe a test case.

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

It is guaranteed that the sum of lengths of strings over all test cases does not exceed 106106.

Output

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

Example

Input

5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

Output

a
abcdfdcba
xyzyx
c
abba

Note

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

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

• Its length is 99, which does not exceed the length of the string ss, which equals 1111.
• It is a palindrome.
• "abcdfdcba" == "abcdfdc" ++ "ba", and "abcdfdc" is a prefix of ss while "ba" is a suffix of ss.

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 aa or bb can be empty. The other possible solution for this test is "s".

题意：

给你一个有小写字母组成的字符串s，你需要找出来一个s的前缀a，和s的后缀b，使得a、b拼接起来是一个回文串t，我们要保证a字符串的长度加上b字符串的长度要小于s字符串长度

输出最长的回文串t

题解：

可以先用while循环找出来前面和后面相等长度，再对剩下的字符串用manacher求包含边界的最长回文。

例如：abacsjsba。我们用while循环找到左边的ab和右边的ba，剩下acsjs，再找该字符串包含边界的最大回文串，显然是sjs，最后ab+sjs+ba就是答案。

这里要注意，我们求的是包含边界的最大回文串，例如剩下的字符串为aacddcb，那么我们只能输出aa而不能输出cddc，因为我们求的是最长前缀和最长后缀拼接而成的最长回文串

正确代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 const int maxn=1e6+10;
8 const int INF=0x3f3f3f3f;
9 const int mod=998244353;
10 using namespace std;
11 string Manacher(const string &s)
12 {
13 string t="#";
14 for(char c:s) t+=c,t+="#";
15 /*
16 两种解法的唯一区别在于第一种解法使用了
17 for (char& c : s)
18 第二种使用了
19 for (char c : s)
20 结果是第一种方法比第二种方法快得多。虽然原因很简单，只是一个很基本的道理，但是毕竟初学，还是写下来记录一下。
21 使用
22 for (char c : s)
23 时会复制一个s字符串再进行遍历操作，而使用
24 for (char& c : s)
25 时直接引用原字符串进行遍历操作，由于复制一个字符串花费了大量的时间，所以第一种解法要快于第二种解法。
26 链接：https://blog.csdn.net/edjoker2/article/details/79383536
27 */
28 int Len[t.size()]= {0};
29 int sum=0;
30 int pos=0;
31 for(int i=0; i=0&&i+Len[i]sum)
40 pos=i,sum=Len[i]+i-1;
41 }
42 int MaxLen=0;
43 for(int i=0; i>s;
52 int l=0,r=s.size()-1;
53 while(l
59 reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值
60 */
61 s1=Manacher(s1);
62 s2=Manacher(s2);
63 cout<s2.size()?s1:s2)<>t;
69 while(t--)
70 solve();
71 return 0;
72 }

我原本求回文串的时候没有注意还要包含边界，导致一直错。。。这里代码也给一下，有可能其他题用得到

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 const int maxn=1e7+10;
8 const int INF=0x3f3f3f3f;
9 const int mod=998244353;
10 char str[maxn],s[maxn],ptr[maxn];
11 int len,Len[maxn],index;
12 void init()
13 {
14 memset(str,0,sizeof(str));
15 int k=0;
16 str[k++]='$';
17 for(int i=0; imx)
33 {
34 mx=Len[i]+i;
35 id=i;
36 if(sum=0; --i)
72 printf("%c",ptr[i]);
73 printf("\n");
74 continue;
75 }
76 len=0;
77 for(int i=num; i<=lenn-num; ++i) 78 { 79 s[len++]=ptr[i]; 80 } 81 init(); 82 int ans=manacher(); 83 for(int i=0; i0)
99 {
100 for(int i=num-1; i>=0; --i)
101 printf("%c",ptr[i]);
102 }
103 printf("\n");
104 }
105 return 0;
106 }
107 //0 1 2 3 4 5 6 7 8
108 // 1 2 3 4

用这个代码在codeforces上提交的时候第二组样例错了