1250번 - 색칠된 공들

문제

규완이는 N개의 순서대로 색칠된 공을 가지고 있다. (색은 영어 대문자로 이루어져 있다.) 당신은 이 공을 가지고 다음과 같은 재미있는 일을 하고자 한다.

1. 가장 많은 개수로 같은 색이 연속된 공을 제거한다.
2. 만약 가장 많은 개수로 같은 색이 연속된 부분이 여럿 있다면, 그 중에서 맨 앞에 있는 부분을 제거한다.
3. 1, 2를 공이 모두 제거될 때 까지 반복한다.

이 과정을 반복하던 도중, 규완이는 k 번째 공이 몇 번째 사라질지 궁금해졌다. 규완이를 도와주자.

입력

첫째 줄에는 공의 개수인 N과, 자신이 언제 없어지는지 알고 싶은 공의 번호 k가 주어진다. 그 다음 줄에는 공의 색이 연속된 N개의 문자열로 주어진다. (1 ≤ N ≤ 10000000)

출력

그 k번째 공이 사라지는 시행횟수가 몇 번째인지 출력한다.

제한

힌트

• 0 : AABAABBBCD
• 1 : AABAACD
• 2 : BAACD
• 3 : BCD