Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛，但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说「现在是哞哞时间！谁想哞哞？请，我只想参加 USACO」。
Bessie 仍然不理解，于是她将 Elsie 的描述转文字得到了一个长为 （）的字符串，包含小写字母字符 。Elsie 认为一个包含三个字符的字符串 是一个哞叫，如果 且 。
一个三元组 是合法的，如果 且字符串 组成一个哞叫。对于该三元组，FJ 执行以下操作计算其值：
换句话说，该三元组的值等于 。
Bessie 向你进行 （）个查询。在每个查询中，她给你两个整数 和 （，），并询问满足 和 的所有合法三元组 的最大值。如果不存在合法的三元组，输出 。
注意这个问题涉及到的整数可能需要使用 64 位整数类型（例如，C/C++ 中的 long long）。
long long
输入的第一行包含两个整数 和 。 以下一行包含 。
以下 行每行包含两个整数 和 ，表示每个查询。
对于每一个查询输出一行，包含对于该查询的答案。
12 5 abcabbacabac 1 12 2 7 4 8 2 5 3 10
28 6 1 -1 12
样例解释：对于第一个查询， 必须满足 。可以证明，对于某个合法的 ， 的最大面积在 ， 以及 时取到。注意 是字符串 "acc"，根据前述定义是一个哞叫。 的直角边长为 和 ，从而它的面积的两倍将等于 。 对于第三个查询， 必须满足 。可以证明，对于某个合法的 ， 的最大面积在 ， 以及 时取到。
对于第四个查询，不存在满足 的 使得 是一个哞叫，所以该查询的输出为 。