本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Elsie 正在向 Bessie 描述她最喜欢的 USACO 比赛，但 Bessie 很难理解为什么 Elsie 如此喜欢它。Elsie 说：“And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO”。 Bessie 还是不明白，于是她将 Elsie 的描述抄写成一个长度为 $N$（$3 \leq N \leq 10^5$）的字符串，包含小写英文字母 $s_1s_2 \ldots s_N$。Elsie 认为一个包含三个字符的字符串 $t$ 是一个 moo，当且仅当 $t_2 = t_3$ 且 $t_2 \neq t_1$。 当三元组 $(i, j, k)$ 满足 $i < j < k$ 且字符串 $s_i s_j s_k$ 构成一个 moo 时，该三元组是有效的。对于该三元组，FJ 按如下方式计算其价值： FJ 在下标 $j$ 处将字符串 $s$ 弯折 90 度。 三元组的价值是三角形 $\Delta ijk$ 面积的两倍。 换句话说，该三元组的价值为 $(j-i)(k-j)$。 Bessie 会问你 $Q$（$1 \leq Q \leq 3 \cdot 10^4$）个询问。在每个询问中，她给出两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq N$, $r-l+1 \ge 3$），并要求你在所有满足 $l \leq i$ 且 $k \leq r$ 的有效三元组 $(i, j, k)$ 中，输出其价值的最大值。如果不存在有效三元组，则输出 $-1$。 注意：本题中涉及的整数可能很大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

输入格式

第一行包含两个整数 $N$ 和 $Q$。 第二行包含 $s_1 s_2, \ldots s_N$。 接下来 $Q$ 行每行包含两个整数 $l$ 和 $r$，表示一个询问。

输出格式

对每个询问输出一行答案。

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

28
6
1
-1
12

提示

对于第一个询问，$(i,j,k)$ 必须满足 $1 \le i < j < k \le 12$。可以证明，某个有效 $(i,j,k)$ 使得 $\Delta ijk$ 的最大面积在 $i=1$, $j=8$, $k=12$ 时取得。注意 $s_1 s_8 s_{12}$ 为字符串 "acc"，根据上述定义它是一个 moo。$\Delta ijk$ 的两条直角边长度分别为 $7$ 和 $4$，因此其面积的两倍为 $28$。 对于第三个询问，$(i,j,k)$ 必须满足 $4 \le i < j < k \le 8$。可以证明，某个有效 $(i,j,k)$ 使得 $\Delta ijk$ 的最大面积在 $i=4$, $j=5$, $k=6$ 时取得。 对于第四个询问，不存在满足 $2 \le i < j < k \le 5$ 且 $s_i s_j s_k$ 为 moo 的 $(i,j,k)$，因此该询问的输出为 $-1$。 SCORING: Inputs 2-3: $N,Q\le 50$ Inputs 4-6: $Q=1$ 且唯一的询问满足 $l=1$ 且 $r=N$ Inputs 7-11: 无额外限制 Problem credits: Chongtian Ma

来源

USACO|2025|Bronze