한 줄의 조용한 객석

문제

작은 공연장에서 낭독 공연을 준비하고 있다. 무대 앞의 긴 객석 한 줄에는 N개의 좌석이 있으며, 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 점검 담당자는 각 좌석에 앉았을 때 소리가 나는지 확인하여 점검표를 만들었다. 점검표의 i번째 문자가 0이면 i번 좌석은 조용한 좌석이고, 1이면 앉을 때 소리가 나는 좌석이다. 공연장에는 소리가 나는 좌석을 조용하게 만드는 완충재가 K개 있다. 완충재 하나는 좌석 하나에만 설치할 수 있으며, 설치한 좌석은 공연이 끝날 때까지 조용한 좌석이 된다. 완충재를 모두 사용할 필요는 없다. 좌석의 순서를 바꾸거나 좌석을 다른 위치로 옮기는 것은 허용하지 않는다. 운영자는 관객 한 모임을 서로 이웃한 좌석에 앉히려고 한다. 이를 위해 시작 번호 L과 끝 번호 R을 정하고, L번부터 R번까지의 모든 좌석을 모임에 배정한다. 배정 구간 안에서는 빈 좌석을 남길 수 없으며, 구간에 포함된 모든 좌석이 조용해야 한다. 처음부터 조용한 좌석은 그대로 사용하고, 소리가 나는 좌석에는 완충재를 설치하면 된다. 따라서 배정 구간에 처음부터 소리가 나는 좌석이 K개 이하라면 그 구간을 사용할 수 있다. 구간 밖에 있는 좌석의 상태는 배정 가능 여부에 영향을 주지 않는다. 사용할 수 있는 연속 구간 중 좌석 수가 가장 많은 구간을 구해야 한다. 좌석 수가 같은 구간이 여러 개라면 시작 번호 L이 가장 작은 구간을 선택한다. 선택한 구간의 좌석 수와 양 끝 번호를 출력한다. 한 좌석도 배정할 수 없다면 구간을 선택하지 않고 세 수 0 0 0을 출력한다. 모든 좌석을 사용할 수 있는 경우에는 전체 구간을 선택한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000이고 0 ≤ K ≤ N이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어져 있으며, i번째 문자는 i번 좌석의 점검 결과를 나타낸다.

출력

선택한 구간의 좌석 수, 시작 번호 L, 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 가능한 구간 중 좌석 수가 최대여야 하며, 동점이면 L이 가장 작아야 한다. 사용할 수 있는 좌석이 하나도 없으면 0 0 0을 출력한다.

8 1
00100110

5 1 5

6 0
111111

0 0 0

7 2
1010101

5 2 6

출처: Devin.KR 자체 제작