题目描述

Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛，但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说「现在是哞哞时间！谁想哞哞？请，我只想参加 USACO」。

Bessie 仍然不理解，于是她将 Elsie 的描述转文字得到了一个长为 $N$（$3 \leq N \leq 10^5$）的字符串，包含小写字母字符 $s_1s_2 \ldots s_N$。Elsie 认为一个包含三个字符的字符串 $t$ 是一个哞叫，如果 $t_2 = t_3$ 且 $t_2 \neq t_1$。

一个三元组 $(i, j, k)$ 是合法的，如果 $i < j < k$ 且字符串 $s_i s_j s_k$ 组成一个哞叫。对于该三元组，FJ 执行以下操作计算其值：

• FJ 将字符串 $s$ 在索引 $j$ 处弯曲 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"，根据前述定义是一个哞叫。$\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$ 的 $(i,j,k)$ 使得 $s_i s_j s_k$ 是一个哞叫，所以该查询的输出为 $-1$。

• 测试点 $2\sim3$：$N,Q\le 50$。
• 测试点 $4\sim6$：$Q=1$，唯一的询问满足 $l=1$ 且 $r=N$。
• 测试点 $7\sim 11$：没有额外限制。