Mùa Moo III

Elsie mô tả một kỳ thi USACO bằng xâu $s$ độ dài $N$ gồm các chữ cái thường. Một "moo" là xâu ba ký tự $t$ thỏa mãn $t_2=t_3$ và $t_2\ne t_1$.

Bộ ba $(i,j,k)$ với $i<j<k$ là hợp lệ nếu $s_i{s}_j{s}_k$ tạo thành một "moo". Giá trị của bộ ba đó là $(j-i)\times (k-j)$.

Với $Q$ truy vấn, mỗi truy vấn cho $l$ và $r$, tìm giá trị lớn nhất trong các bộ ba hợp lệ $(i,j,k)$ với $l\le i$ và $k\le r$, hoặc trả về $-1$ nếu không tồn tại.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $Q$.
• Dòng 2: Xâu $s$ độ dài $N$.
• $Q$ dòng tiếp theo: Hai số nguyên $l$, $r$.

Dữ liệu ra

• $Q$ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Ràng buộc

• $3\le N\le {10}^5$
• $1\le Q\le 3\times {10}^4$
• $1\le l\le r\le N$, $r-l+1\ge 3$

Ví dụ