사전순 강의

독일의 유명한 대학인 OUG("Ordered University of Germany")에는 학생이 아주 많아서, 학번이 모두 같은 길이 $\ell$인 긴 문자열이다. 학번에는 영어 소문자만 들어간다. 안타깝게도 이 대학의 총장은 무질서를 싫어해서, 학생들은 항상 학번의 사전순으로 강의실에 들어와야 한다. 짐작할 수 있듯이, 강의실 앞에서 학생들이 줄을 서는 데는 꽤 많은 시간이 걸린다. 전산학과 학생인 Georgina는 이 과정을 빠르게 할 방법을 떠올렸다. 정수 $i, j$를 $1 \leq i \leq j \leq \ell$로 고정해, 학번의 $i$번째 글자부터 $j$번째 글자까지의 부분 문자열을 기준으로 삼는 것이다. 그러면 학생들은 학번의 이 부분 문자열을 기준으로 사전순으로 줄을 선다. 물론, 이 새로운 순서가 전체 학번을 기준으로 한 사전순과 같아지도록 $i$와 $j$를 골라야 한다. 과정을 최대한 빠르게 하려면 부분 문자열의 길이가 최소여야 한다. Georgina가 이 문제를 해결하도록 도와줄 수 있는가?

입력은 다음과 같다.

• 두 정수 $n$과 $\ell$이 있는 한 줄

  • $n$ ($2 \leq n \leq 500$)은 학번의 개수다.
  • $\ell$ ($1 \leq \ell \leq 2 \cdot 10^4$)은 각 학번의 길이다.

• $n$개의 줄. $i$번째 줄에는 $i$번째 학생의 학번이 들어 있다.

모든 학번에는 영어 소문자만 들어가며, 서로 다르고 사전순으로 주어진다.

학번의 어떤 부분 문자열을 기준으로 학생들이 사전순으로 줄을 섰을 때 전체 학번을 기준으로 사전순으로 줄을 섰을 때와 같은 순서가 되게 하는 가장 짧은 부분 문자열의 첫 글자와 마지막 글자의 인덱스를 나타내는 두 정수를 출력한다.

가장 짧은 부분 문자열이 여러 개라면, 그중 아무거나 출력해도 된다.