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 $N$ ( $3 \leq N \leq 1 0^{5}$ ) containing lowercase alphabetic characters $s_{1} s_{2} \dots s_{N}$ . Elsie considers a string $t$ containing three characters a moo if $t_{2} = t_{3}$ and $t_{2} \neq = t_{1}$ .

A triplet $(i, j, k)$ is valid if $i < j < k$ and string $s_{i} s_{j} s_{k}$ forms a moo. For the triplet, FJ performs the following to calculate its value:

FJ bends string $s$ 90-degrees at index $j$
The value of the triplet is twice the area of $Δ ij k$ .

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

Bessie asks you $Q$ ( $1 \leq Q \leq 3 \cdot 1 0^{4}$ ) queries. In each query, she gives you two integers $l$ and $r$ ( $1 \leq l \leq r \leq N$ , $r - l + 1 \geq 3$ ) and ask you for the maximum value among valid triplets $(i, j, k)$ such that $l \leq i$ and $k \leq r$ . If no valid triplet exists, output $- 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++).

For the first query, ( $i, j, k$ ) must satisfy $1 \leq i < j < k \leq 12$ . It can be shown that the maximum area of $Δ ij k$ for some valid ( $i, j, k$ ) is achieved when $i = 1$ , $j = 8$ , and $k = 12$ . Note that $s_{1} s_{8} s_{12}$ is the string "acc" which is a moo according to the definitions above. $Δ ij k$ will have legs of lengths $7$ and $4$ so two times the area of it will be $28$ .

For the third query, ( $i, j, k$ ) must satisfy $4 \leq i < j < k \leq 8$ . It can be shown that the maximum area of $Δ ij k$ for some valid ( $i, j, k$ ) is achieved when $i = 4$ , $j = 5$ , and $k = 6$ .

For the fourth query, there exists no ( $i, j, k$ ) satisfying $2 \leq i < j < k \leq 5$ in which $s_{i} s_{j} s_{k}$ is a moo so the output to that query is $- 1$ .

SCORING:

Inputs 2-3: $N, Q \leq 50$
Inputs 4-6: $Q = 1$ and the singular query satisfies $l = 1$ and $r = N$
Inputs 7-11: No additional constraints

Problem credits: Chongtian Ma

Source: USA Computing Olympiad.

Input Format

The first line contains two integers $N$ and $Q$ .

The following line contains $s_{1} s_{2}, \dots s_{N}$ .

The following $Q$ lines contain two integers $l$ and $r$ , denoting each query.

Output Format

Output the answer for each query on a new line.

Sample Input

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

Sample Output

28 6 1 -1 12

Submit

Language