문제

승현이는 성현이에게 자신이 가장 좋아하는 알고리즘 문제를 설명해 주려 한다. 하지만 성현이는 승현이가 왜 이 문제를 좋아하는지 잘 이해하지 못하고 있다. 승현이는 "자, 이제 '음메'할 시간이야! 누가 '음메'를 하고 싶어? 제발, 난 그냥 알고리즘 문제를 풀고 싶을 뿐이야."라고 말한다.

성현이는 여전히 이해하지 못해서, 승현이가 설명한 내용을 바탕으로 길이가 $N$ ($3 \le N \le 10^5$)인 소문자 알파벳으로 이루어진 문자열 $s_1 s_2 \ldots s_N$을 적었다. 승현이는 세 개의 문자로 이루어진 문자열 $t$가 $t_2 = t_3$이고 $t_1 \neq t_2$를 만족하면, 이 문자열을 **"음메"**라고 부른다.

세 인덱스의 순서쌍 $(i, j, k)$가 $i < j < k$를 만족하고, 문자열 $s_i s_j s_k$가 "음메"를 형성하면 이 순서쌍은 유효하다고 한다. 이때 이 순서쌍의 값은 $(j-i)(k-j)$이다. (이는 $j$에서 90도로 꺾인 삼각형 $ijk$의 넓이를 두 배한 것과 같다.)

성현이는 당신에게 $Q$ ($1 \le Q \le 3 \cdot 10^4$)개의 쿼리를 던진다. 각 쿼리는 두 정수 $l$과 $r$ ($1 \le l \le r \le N$, $r-l+1 \ge 3$)로 주어지며, $l \le i$이고 $k \le r$을 만족하는 유효한 순서쌍 $(i, j, k)$ 중 값의 최댓값을 구해야 한다. 만약 유효한 순서쌍이 존재하지 않는다면 $-1$을 출력한다.

이 문제에서 다루는 정수의 값이 매우 클 수 있으므로 64비트 정수 자료형(C/C++의 long long 등)을 사용하는 것을 권장한다.

입력

첫째 줄에 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. ($3 \le N \le 10^5$; $1 \le Q \le 3 \cdot 10^4$)

둘째 줄에 길이가 $N$인 문자열 $s_1 s_2 \ldots s_N$이 주어진다.

이어서 $Q$개의 줄에 각 쿼리를 나타내는 두 정수 $l$과 $r$이 공백으로 구분되어 주어진다. ($1 \le l \le r \le N$; $r-l+1 \ge 3$)

출력

각 쿼리에 대한 정답을 새로운 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

28
6
1
-1
12

점수

• 테스트 케이스 2~3: $N, Q \le 50$
• 테스트 케이스 4~6: $Q = 1$이며, 해당 쿼리는 $l = 1$, $r = N$을 만족한다.
• 테스트 케이스 7~11: 추가 제약 조건이 없다.