Elsie đang cố kể cho Bessie nghe về kỳ thi USACO yêu thích của mình, nhưng Bessie không hiểu tại sao Elsie lại thích nó đến vậy. Elsie nói: “And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO”.

Bessie vẫn không hiểu, nên cô chép lại lời kể của Elsie thành một xâu độ dài \(N\) (\(3 \leq N \leq 10^5\)) gồm các chữ cái tiếng Anh viết thường \(s_1s_2\ldots s_N\). Elsie gọi một xâu \(t\) gồm ba ký tự là một moo nếu \(t_2=t_3\) và \(t_2\neq t_1\).

Một bộ ba \((i,j,k)\) là hợp lệ nếu \(i<j<k\) và xâu \(s_i s_j s_k\) tạo thành một moo. Với bộ ba đó, FJ thực hiện như sau để tính giá trị:

• FJ bẻ xâu \(s\) một góc 90 độ tại chỉ số \(j\).
• Giá trị của bộ ba bằng hai lần diện tích tam giác \(\Delta ijk\).

Nói cách khác, giá trị của bộ ba là \((j-i)(k-j)\).

Bessie hỏi bạn \(Q\) (\(1 \leq Q \leq 3\cdot 10^4\)) truy vấn. Trong mỗi truy vấn, cô đưa ra hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1\ge 3\)) và yêu cầu giá trị lớn nhất trong các bộ ba hợp lệ \((i,j,k)\) sao cho \(l\le i\) và \(k\le r\). Nếu không tồn tại bộ ba hợp lệ, in ra \(-1\).

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu số nguyên 64-bit (chẳng hạn long long trong C/C++).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).

Dòng tiếp theo chứa \(s_1s_2\ldots s_N\).

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\), mô tả một truy vấn.

Dữ liệu ra

In đáp án của mỗi truy vấn trên một dòng riêng.

Ví dụ

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

28
6
1
-1
12

Phân nhóm

• Dữ liệu 2–3: \(N,Q\le 50\).
• Dữ liệu 4–6: \(Q=1\) và truy vấn duy nhất thỏa mãn \(l=1\), \(r=N\).
• Dữ liệu 7–11: Không có ràng buộc bổ sung.

Đề bài: Chongtian Ma.

Nguồn

USACO 2025 US Open Contest, Bronze — It's Mooin' Time III: https://usaco.org/index.php?page=viewproblem2&cpid=1517