H. PalindromePalindrometime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputWe define the humor value of a string $$$t$$$ as the length of the longest palindrome string which occurs at least twice in it.Formally, a string $$$p$$$ is humor with respect to $$$t$$$, if and only if both of the following conditions are met: $$$p$$$ is a palindrome, and there exist at least two different indices $$$i \in [1, |t| - |p| + 1]$$$, such that $$$t[i, i + |p| - 1] = p$$$. The humor value of $$$t$$$ is defined as the maximum length among all humor strings with respect to $$$t$$$.You are given a string $$$s$$$ of length $$$n$$$ which only contains lowercase Latin letters and $$$q$$$ queries. Each query contains two integers $$$l_i$$$, $$$r_i$$$, and you need to find the humor value of the string $$$s[l_i, r_i]$$$.Here, $$$a[l, r]$$$ is defined as the string $$$a_l,a_{l+1},\ldots,a_r$$$.InputThe first line contains two integers $$$n$$$, $$$q$$$ ($$$1\le n,q\le 5\cdot10^5$$$).The second line contains a string $$$s$$$.The next $$$q$$$ lines contain the description of queries. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$).OutputOn the $$$i$$$-th line, output the answer to the $$$i$$$-th query.ExampleInput12 6aaaabbbbaaaa1 122 73 104 75 94 5Output4
2
3
2
3
0
NoteIn the first query, the following palindrome strings occur at least twice: a,aa,aaa,aaaa,b,bb,bbb. The longest one is aaaa, so the humor value is $$$4$$$.In the second query, one of the longest humor strings with respect to $$$s[2, 7]$$$ is aa.