28140번 - 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕! 스페셜 저지

알파벳 대문자로 이루어진 길이 $N$의 문자열 $S=S_0S_1S_2\cdots S_{N-1}$가 주어진다.

구간 $[l, r]$이 주어질 때, 아래의 규칙을 만족하는 정수 $a,\ b,\ c,\ d$를 찾으면 당신은 달콤한 솜사탕을 얻을 수 있다.

• $S_a=S_b=$R
• $S_c=S_d=$B
• $l \leq a \lt b \lt c \lt d \leq r$

구간이 $Q$번 주어질 때 달콤한 솜사탕을 얻을 수 있으면 그때의 $a,\ b,\ c,\ d$를 아무거나 하나 출력하고, 얻을 수 없으면 -1을 출력한다.

첫째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. ($4 \le N \le 1\ 000\ 000;\ 1 \le Q \le 1\ 000\ 000$)

둘째 줄에 문자열 $S$가 주어진다.

다음 $Q$개의 줄에 두 정수 $l$, $r$이 공백으로 구분되어 주어진다. ($0 \le l \le r \le N-1$)

매 쿼리마다 달콤한 솜사탕을 얻을 수 있는 경우 가능한 $a,\ b,\ c,\ d$를 아무거나 하나 공백으로 구분하여 출력하고, 솜사탕을 얻을 수 없는 경우 -1을 출력한다.