32253번 - 여우 셰프 스페셜 저지

문제

여우 마을에 사는 여우들에게도 내집마련은 중요한 문제이다. 얼마 전, 드디어 독립에 성공한 아기 여우를 축하하기 위해 친구들이 아기 여우네 집에 모이기로 했다.

아기 여우는 일일 셰프가 되어 고마운 친구들에게 음식을 대접하기로 결정했다.

아기 여우는 애피타이저로 여우가 그려진 귀여운 쿠키를 $N$개 준비해서, 긴 접시에 일렬로 담아 내려고 한다. 그런데 아뿔싸, 접시를 식탁에 내려놓다 몇몇 쿠키들이 뒤집히고 말았다. 이대로 손님들이 온다면 아기 여우가 음식을 대충 준비했다고 생각할지도 모른다!

아기 여우는 집게를 이용해서 쿠키를 다시 뒤집으려고 한다. 연속한 쿠키들은 한 번에 뒤집을 수 있으며, 집게의 크기에 비해 쿠키의 크기가 너무 작아 한 번 뒤집을 때 최소 $K$개의 연속한 쿠키를 같이 뒤집어야 한다. 아기 여우의 목적은 손님들에게 정돈된 인상을 주는 것이므로, 쿠키들이 모두 같은 면으로 놓여 있다면 앞면이든 뒷면이든 신경 쓰지 않기로 했다.

손님들이 올 시간이 얼마 남지 않았다! 하지만 아기 여우에게는 지금 쿠키 말고도 신경 쓸 요리가 너무 많다. 바쁜 아기 여우를 위해 집게를 이용해서 쿠키를 모두 같은 면으로 만드는 것이 가능한지, 가능하다면 어떻게 하면 집게를 최소로 사용할 수 있는지 구해 알려주자!

입력

첫째 줄에 양의 정수 $N,ドル $K$가 공백을 사이에 두고 주어진다. (1ドル\le K\le N\le 500,円 000$)

둘째 줄에 길이가 $N$이고 O, X만으로 이루어진 문자열이 주어진다. 이는 초기 쿠키의 상태를 나타내며, $i$번째 문자가 O라면 $i$번째 쿠키가 앞면으로 놓여 있으며, X라면 뒷면으로 놓여 있다는 의미이다.

출력

어떻게 집게를 사용하더라도 모든 쿠키가 같은 면으로 놓이도록 할 수 없으면 첫째 줄에 -1을 출력한다.

모든 쿠키가 같은 면으로 놓이도록 만들 수 있다면, 첫째 줄에 집게를 사용하는 최소 횟수 $M$을 출력한다. ($M\ge 0$)

다음 $M$개의 줄에 집게를 사용하는 방법을 한 줄에 하나씩 차례대로 출력한다. $i$번째 쿠키부터 $j$번째 쿠키를 뒤집는다면 $i$와 $j$를 공백을 사이에 두고 출력한다. (1ドル\le i\le j\le N$; $j-i\ge K-1$)

제한

노트

집게를 이용해 쿠키의 위치를 바꿀 수는 없다. 제자리에서 앞/뒷면 상태를 바꾸는 것만 가능하다.