색칠된 공들

규완이는 왼쪽부터 오른쪽까지 일렬로 놓인 N개의 공을 가지고 있다. 각 공의 색은 영어 대문자 하나로 표시된다.

공이 모두 없어질 때까지 다음 과정을 반복한다.

1. 현재 남아 있는 공들 중에서 같은 색이 연속된 가장 긴 묶음을 찾는다.
2. 그런 묶음이 여러 개라면, 가장 왼쪽에 있는 묶음을 선택한다.
3. 선택한 묶음의 공을 모두 제거한다.

처음에 왼쪽에서 k번째였던 공이 몇 번째 시행에서 제거되는지 구하라.

첫째 줄에 공의 개수 N과 제거되는 시점을 알고 싶은 공의 번호 k가 주어진다.

둘째 줄에 길이가 N인 문자열이 주어진다. 문자열의 각 문자는 해당 위치 공의 색을 나타내는 영어 대문자이다.

제한: 1 ≤ k ≤ N ≤ 10,000,000

처음에 왼쪽에서 k번째였던 공이 제거되는 시행 번호를 출력한다.

공을 제거한 뒤 양쪽에 남은 묶음이 같은 색이면 두 묶음은 서로 붙어 하나의 더 긴 묶음이 된다. 이후 시행에서는 이렇게 합쳐진 묶음의 길이를 기준으로 다시 가장 긴 묶음을 고른다.