Moo Time Queries

Elsie is trying to explain her favorite USACO competition to Bessie, but Bessie just can’t understand why Elsie is so fond of it. Elsie exclaims, "Now it's moo time! Who wants to moo? Please, I only want to participate in USACO."

Bessie transcribes Elsie’s spoken words into a string s of length \(N\) (\(3 \le N \le 10^5\)) consisting of lowercase letters \(s_1s_2\ldots s_N\). According to Elsie, a three‐character string \(t\) is a moo‐call if \(t_2=t_3\) and \(t_2\ne t_1\).

A triple \((i,j,k)\) is valid if \(i<j<k\) and the characters \(s_i,s_j,s_k\) form a moo‐call. For every valid triple, Farmer John computes its value by virtually bending the string s at position \(j\) by \(90^\circ\); the value is equal to twice the area of the triangle \(\Delta ijk\), i.e.:

[ \text{value} = (j-i)\times(k-j),. ]

Bessie will ask you \(Q\) (\(1 \le Q \le 3 \cdot 10^4\)) queries. In each query, you are given two integers \(l\) and \(r\) (\(1 \le l \le r \le N\) with \(r-l+1\ge3\)). Your task is to determine the maximum value over all valid triples \((i,j,k)\) with \(l\le i<j<k\le r\). If there is no valid triple in the interval, output -1.

Note: The answer may be very large; make sure to use 64-bit integer types where applicable.

inputFormat

The first line contains two integers \(N\) and \(Q\) --- the length of the string and the number of queries.

The second line contains a string \(s\) of lowercase English letters of length \(N\).

Each of the following \(Q\) lines contains two integers \(l\) and \(r\) representing a query.

It is guaranteed that \(3 \le N \le 10^5\), \(1 \le Q \le 3 \cdot 10^4\), and \(r-l+1\ge3\).

outputFormat

For each query, output the maximum value computed among all valid triples \((i,j,k)\) in the given range. If no valid triple exists, print -1.

sample

5 3
a b b a a
1 5
2 4
3 5

2
-1
1