말 더듬는 외계인

엘리 애로웨이 박사가 외계 문명과 교신에 성공했다. 그러나 지금까지 그들의 메시지를 해독하려는 모든 시도는 실패했는데, 하필이면 그 외계 종족이 말을 더듬는 종족이었기 때문이다. 연구팀은 충분히 긴 메시지라면 가장 중요한 단어들이 연속된 문자열로 여러 번 반복되어 나타나며, 심지어 다른 단어 한가운데에도 끼어들어 등장한다는 사실을 알아냈다. 게다가 그들은 때때로 알기 어려운 방식으로 축약을 사용한다. 예를 들어 bab을 두 번 말해야 한다면, 첫 단어의 두 번째 b를 두 번째 단어의 첫 b로 재사용하여 babab이라는 메시지로 줄여 보낼 수 있다.

이렇게 메시지에는 같은 단어가 서로 겹칠 수도 있는 형태로 몇 번이고 반복되어 담긴다. 당신의 임무는 다음과 같다.

정수 $m$과 메시지를 나타내는 문자열 $s$가 주어질 때, $s$ 안에서 $m$번 이상 등장하는 가장 긴 부분 문자열의 길이를 구하라. 등장 횟수를 셀 때 서로 겹치는 등장도 모두 인정한다. 예를 들어 메시지 baaaababababbababbab에서 길이 5인 단어 babab은 위치 5, 7, 12에서 총 3번 등장한다(위치는 0부터 시작한다). 3번 이상 등장하는 부분 문자열 중 이보다 더 긴 것은 없다. 또한 이 문자열에서 11번 이상 등장하는 부분 문자열은 존재하지 않는다.

가장 긴 부분 문자열이 여러 개라면, 등장 위치가 가장 오른쪽(가장 큰 시작 위치)인 것을 택한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 최소 반복 횟수를 나타내는 정수 $m$($m \ge 1$)이 적힌 한 줄과, 그 다음 줄에 오는 문자열 $s$로 구성된다. $s$의 길이는 $m$ 이상 $40,000$ 이하이며, $s$의 모든 문자는 소문자 a부터 z까지이다. 마지막 테스트 케이스는 $m = 0$으로 표시되며, 이 케이스는 처리하지 않는다.

각 테스트 케이스마다 한 줄씩 출력한다. 해가 없으면 none을 출력한다. 그렇지 않으면 두 정수를 공백으로 구분하여 출력한다. 첫 번째 정수는 $m$번 이상 등장하는 부분 문자열의 최대 길이이고, 두 번째 정수는 그러한 부분 문자열의 가장 오른쪽 시작 위치(0부터 시작)이다.