가장 오래 이어진 관측

문제

작은 날씨 관측소는 일정한 시간 간격으로 하늘의 상태를 확인하고, 확인한 결과를 문자 하나로 기록한다. 맑음은 S, 흐림은 C, 비는 R, 눈은 W로 나타낸다. 장비가 정상적으로 측정하지 못한 시각에는 물음표 ?를 기록한다. 하루의 기록은 측정한 순서대로 문자를 이어 붙인 하나의 문자열로 보관한다. 관측 담당자는 같은 날씨가 끊기지 않고 가장 오래 관측된 구간을 찾아 안내판에 표시하려 한다. 하나의 구간은 문자열에서 서로 이웃한 위치들로 이루어져야 하며, 구간 안의 모든 문자가 같은 날씨 문자여야 한다. 구간의 길이는 그 안에 들어 있는 문자의 개수다. 기록의 위치는 왼쪽부터 1번, 2번, …, N번으로 센다. 실제 측정 간격을 분 단위로 환산할 필요는 없다. 물음표는 어떤 날씨도 나타내지 않으며, 유효한 구간에 포함할 수 없다. 또한 물음표를 사이에 둔 두 기록은 같은 문자여도 하나의 구간으로 합칠 수 없다. 서로 다른 날씨 문자가 만나는 곳에서도 구간이 끊어진다. 기록의 마지막 문자와 첫 번째 문자는 서로 이웃하지 않는다. 날씨 문자가 하나만 있는 구간도 길이가 1인 유효한 구간이다. 길이가 가장 긴 구간이 여러 개라면 시작 위치가 가장 작은 구간을 선택한다. 날씨 문자의 사전순이나 날씨의 종류에는 우선순위를 두지 않는다. 문자열에 날씨 문자가 하나라도 있다면 이 규칙으로 선택되는 구간은 하나로 정해진다. 문자열 전체가 물음표라면 선택할 수 있는 구간이 없다. 관측 기록이 주어질 때, 선택한 구간의 날씨 문자와 시작 위치, 길이를 구하는 프로그램을 작성한다. 기록을 수정하거나 물음표의 날씨를 추측해서는 안 된다.

입력

첫째 줄에 기록의 길이인 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 길이가 정확히 N인 문자열이 주어진다. 문자열은 S, C, R, W, ?만으로 이루어지며 공백을 포함하지 않는다.

출력

선택한 구간의 날씨 문자, 시작 위치, 길이를 공백으로 구분하여 한 줄에 출력한다. 유효한 구간이 없으면 NONE 0 0을 출력한다.

12
SSRRR?WWWWCC

W 7 4

8
CC?SS?RR

C 1 2

4
????

NONE 0 0

출처: Devin.KR 자체 제작