Elsie는 Bessie에게 자신이 가장 좋아하는 USACO 대회를 설명하려고 하고 있지만, Bessie는 Elsie가 왜 그것을 그렇게 좋아하는지 이해하는 데 어려움을 겪고 있다.
Elsie는 말한다: "그리고 이제 mooin' 시간이야! 누가 moo 하나 할래? 제발, 그냥 USACO 좀 하고 싶어."

Bessie는 여전히 이해하지 못했고, 그래서 Elsie의 설명을 길이 N (1\le N \le 10^5)인 문자열로 받아 적었다.
이 문자열은 소문자 알파벳 문자들로만 이루어져 있다: s_1 s_2 \dots s_N.

Elsie는 세 문자로 이루어진 문자열 t가 "moo"인지 판단하는 기준을 다음과 같이 정의한다:

t_2 = t_3
t_2 \ne t_1

세 정수 (i, j, k)가 유효하다는 것은 다음을 의미한다:

i < j < k
문자열 s_i s_j s_k가 "moo"이다.

해당 triplet에 대해, FJ는 다음과 같은 계산을 수행한다:

FJ는 문자열 s를 인덱스 j에서 90도로 꺾는다.
triplet의 값은 삼각형 \Delta_{ijk}의 면적의 두 배이다.
다시 말해, triplet의 값은 (j - i)(k - j)이다.

Bessie는 여러분에게 Q개의 질의를 보낸다 (1 \le Q \le 3 \cdot 10^4).
각 질의에서, 그녀는 두 정수 l과 r (1 \le l \le r \le N, r - l + 1 \ge 3)을 주며 다음을 요청한다:

유효한 triplet (i, j, k) 중에서 l \le i < j < k \le r을 만족하는 것들 중, 가장 큰 값을 출력하라.
유효한 triplet이 존재하지 않으면, -1을 출력하라.

이 문제에서 사용되는 정수의 크기가 매우 클 수 있기 때문에, 64비트 정수형 자료형 (예: C/C++의 "long long")을 사용하는 것이 필요할 수 있다.

#8414 upload 5 done 1 how_to_reg 1

It's Mooin' Time III timer 1s memory 1024MB

#8414

It's Mooin' Time III 1s 1024MB