It's Mooin' Time III

문제

Elsie is trying to describe her favorite USACO contest to Bessie, but Bessie is having trouble understanding why Elsie likes it so much. Elsie says "And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO".

Bessie still doesn't understand, so she transcribes Elsie's description in a string of length $NN$ ($3\le N\le {10}^{5}3\; \backslash leq\; N\; \backslash leq\; 10^5$) containing lowercase alphabetic characters $s_1{s}_2\dots s_{N}s\_1s\_2\; \backslash ldots\; s\_N$. Elsie considers a string $tt$ containing three characters a moo if $t_2=t_{3}t\_2\; =\; t\_3$ and $t_2\mathrm{\ne }{t}_{1}t\_2\; \backslash neq\; t\_1$.

A triplet $(i,j,k)(i,\; j,\; k)$ is valid if and string $s_i{s}_j{s}_{k}s\_i\; s\_j\; s\_k$ forms a moo. For the triplet, FJ performs the following to calculate its value:

• FJ bends string $ss$ 90-degrees at index $jj$
• The value of the triplet is twice the area of $\mathrm{\Delta }ijk\backslash Delta\; ijk$.

In other words, the value of the triplet is $(j-i)(k-j)(j-i)(k-j)$.

Bessie asks you $QQ$ ($1\le Q\le 3\cdot {10}^{4}1\; \backslash leq\; Q\; \backslash leq\; 3\; \backslash cdot\; 10^4$) queries. In each query, she gives you two integers $ll$ and $rr$ ($1\le l\le r\le N1\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; N$, $r-l+1\ge 3r-l+1\; \backslash ge\; 3$) and ask you for the maximum value among valid triplets $(i,j,k)(i,\; j,\; k)$ such that $l\le il\; \backslash leq\; i$ and $k\le rk\; \backslash leq\; r$. If no valid triplet exists, output $-1-1$.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

입력

The first line contains two integers $NN$ and $QQ$.

The following line contains $s_1{s}_2,\dots s_{N}s\_1\; s\_2,\; \backslash ldots\; s\_N$.

The following $QQ$ lines contain two integers $ll$ and $rr$, denoting each query.

출력

Output the answer for each query on a new line.

12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10

28
6
1
-1
12