Беси анализирует строку из \(N\) (\(3 \leq N \leq 10^5\)) маленьких латинских букв
\(s_1s_2 \ldots s_N\). Эльза рассматривает строку \(t\), содержащую три символа
как MOO если \(t_2 = t_3\) и \(t_2 \neq t_1\).
Триплет \((i, j, k)\) валидный, если \(i < j < k\) и строка \(s_i s_j s_k\)
формирует MOO. Для этого триплета ФД выполняет следующее, чтобы вычислить его величину
- ФД сгибает строку \(s\) на 90-градусов в индексе \(j\)
- Величина триплета - удвоенная площадь \(\Delta ijk\).
Другими словами, величина триплета есть \((j-i)(k-j)\).
Беси задаёт Вам \(Q\) (\(1 \leq Q \leq 3 \cdot 10^4\)) вопросов.
В каждом вопросе она даёт Вам два целых числа
\(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\)) и
просит Вас определить максимальную величину среди всех валидных триплетов
\((i, j, k)\) таких, что \(l \leq i\) и \(k \leq r\).
Если валидных триплетов нет, выведите \(-1\).
Решение задачи может потребовать использовать 64-й целый тип
(например, "long long" in C/C++).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит два целых числа
\(N\) и
\(Q\).
Следующая строка содержит символы \(s_1 s_2, \ldots s_N\).
Последующие \(Q\) строк содержат по два целых числа \(l\) и \(r\), обозначающих запрос.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите ответ на каждый вопрос в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10
|
28
6
1
-1
12
|