영화관 좌석 정비 구간

문제

한 영화관은 상영을 시작하기 전에 한 줄로 놓인 좌석 일부를 골라 안내 표지를 교체하려 한다. 이 줄에는 N개의 좌석이 있으며 왼쪽부터 1번, 2번, …, N번으로 번호가 붙어 있다. 좌석 상태표에는 각 좌석이 O 또는 X로 표시되어 있다. O는 바로 작업할 수 있는 좌석이고, X는 짐이 놓여 있어 별도의 정리 작업을 먼저 해야 하는 좌석이다. 두 문자는 모두 대문자이며 숫자 0은 사용하지 않는다. 작업팀은 안내 표지를 옮기는 장비의 특성상 비어 있지 않은 연속 구간 하나를 선택해야 한다. 선택한 구간 안의 좌석은 빠짐없이 작업해야 하므로, 중간에 있는 X 좌석을 건너뛰거나 구간을 둘로 나눌 수 없다. 다만 오늘은 정리 인력이 부족하여 선택한 구간 안에 X 좌석이 K개 이하일 때만 작업할 수 있다. O 좌석의 개수에는 별도의 제한이 없다. 구간 바깥에 있는 좌석의 상태는 이번 작업 가능 여부에 영향을 주지 않는다. 관리자는 한 번에 가능한 한 많은 좌석의 표지를 교체하려 한다. 따라서 조건을 만족하는 구간 중 좌석 수가 가장 많은 구간을 선택한다. 길이가 같은 구간이 여러 개라면 가장 왼쪽에서 시작하는 구간을 선택한다. 즉, 시작 좌석 번호가 가장 작은 구간을 선택한다. 선택한 구간의 길이는 마지막 좌석 번호에서 시작 좌석 번호를 뺀 뒤 1을 더한 값이다. K가 0일 수도 있으므로 작업할 수 있는 좌석이 전혀 없는 경우도 생긴다. 이 경우에는 구간을 선택하지 않고 길이와 시작 번호를 모두 0으로 보고한다. 그 밖의 경우에는 선택한 구간의 길이와 시작 좌석 번호를 보고한다. 좌석 상태표와 정리 가능한 좌석 수가 주어졌을 때 관리자가 선택할 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ N ≤ 100,000이며 0 ≤ K ≤ N이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. 각 문자는 대문자 O 또는 X이며, 왼쪽에서 i번째 문자가 i번 좌석의 상태다.

출력

선택한 구간의 길이와 시작 좌석 번호를 공백으로 구분하여 출력한다. 조건을 만족하는 비어 있지 않은 구간이 없으면 0 0을 출력한다.

9 1
OOXOXOOXO

4 1

4 0
XXXX

0 0

6 0
XOOXOO

2 2

출처: Devin.KR 자체 제작