메시지 전달

캐틀린 스타크는 남편 에다드 스타크에게 팰린드롬인 비밀 메시지를 보내려 한다. 그러나 메시지를 그대로 보낼 수는 없다. 라니스터 가문이 반드시 가로챌 것이고, 그러면 캐틀린과 남편은 큰 위험에 처하기 때문이다. 그래서 캐틀린은 메시지를 암호화하기로 했다. 메시지에 글자 몇 개를 덧붙였고, 이제 새 메시지의 부분 문자열을 고른 뒤 그 안에서 최대 $k$개의 문자를 지우면 원래 메시지를 얻을 수 있다.

에다드는 암호화된 메시지를 받았지만 아내가 무엇을 전하려 했는지 한 가지로 확정할 수 없었다. 그래서 원래 메시지의 후보가 될 수 있는 가장 긴 부분 문자열을 찾으려 한다. 즉, 그 부분 문자열에서 $k$개 이하의 문자를 지워 팰린드롬을 만들 수 있어야 한다. $k$는 캐틀린과 에다드가 함께 좋아하는 숫자다. 왕의 오른팔을 도와 이 까다로운 문제를 풀어 달라. 메시지에 담긴 내용을 모르면 그의 목숨이 위험해질 수 있다.

첫 줄에 정수 $k$ ($0 \le k \le 5000$)가 주어진다. 삭제할 수 있는 문자의 최대 개수이다. 둘째 줄에 문자열 $s$ ($1 \le |s| \le 5000$)가 주어진다. 에다드가 받은 메시지이다. 문자열은 영어 소문자로만 이루어져 있다.

공백으로 구분된 두 정수 $l$, $r$ ($1 \le l \le r \le |s|$)을 한 줄에 출력한다. 캐틀린의 메시지 후보가 되는 가장 긴 부분 문자열의 왼쪽 끝과 오른쪽 끝이다. 답이 여러 개이면 왼쪽 끝이 가장 왼쪽에 있는 답을 출력한다.