29100번 - Передача сообщения 다국어

Кейтилин Старк хочет отослать своему мужу Эддарду тайное сообщение, которое является палиндромом. Но сообщение нельзя отсылать просто так --- его определенно перехватят Ланнистеры, и тогда Кейтилин и её мужу несдобровать. Поэтому Кейтилин решила зашифровать своё послание. Она добавила в него несколько букв, и теперь её сообщение можно получить, взяв некоторую подстроку нового послания и удалив из неё не более $k$ символов.

Когда Эддард получил письмо с зашифрованным сообщением, он не смог однозначно определить, что хотела передать ему жена. Но он хочет найти хотя бы самую длинную подстроку, являющуюся кандидатом на сообщение его жены --- подстроку, из которой можно удалить не больше $k$ символов так, чтобы она являлась палиндромом. Число $k$ Эддард знает --- это их любимое с Кейтилин число.

Помогите деснице короля решить эту непростую задачу, ведь незнание информации в присланном сообщении может грозить ему смертью.

В первой строке входного файла дано число $k$ ($0 \le k \le 5000$) --- максимальное количество символов, которое можно удалить.

Во второй строке входного файла дана строка $s$ ($1 \le |s| \le 5000$) --- сообщение, которое получил Эддард.

Сообщение состоит только из строчных букв латинского алфавита.

В единственной строке выходного файла выведите через пробел два числа $l, r$ ($1 \le l \le r \le |s|$), разделенные пробелом --- левый и правый конец наидлиннейшей подстроки, которая является кандидатом на зашифрованное сообщение Кейтилин.

Если возможных ответов несколько, выведите тот, у которого левый конец левее всего.