Hide

Problem L
Lexicographical Lecturing

\includegraphics[width = 0.4\textwidth ]{unsorted.jpg}

The OUG (“Ordered University of Germany") is a renowned German university. Since it has a lot of students, student IDs are quite long strings of equal length $\ell $, where each student ID only contains lowercase letters of the English alphabet. Unfortunately for the students, the university’s president hates chaos and expects students to always enter lecture halls in ascending lexicographic order of their IDs. As you can imagine, the process of sorting themselves in front of the lecture hall takes quite a lot of time for the students. Georgina, a computer science student, has the following idea to accelerate this process: She plans to fix two integers $i,j$ with $1 \leq i \leq j \leq \ell $ denoting a substring of the student ID starting at the $i$th letter and ending in the $j$th letter. Students then sort themselves lexicographically with respect to this substring of their student ID. Of course, $i$ and $j$ must be chosen in a way such that this new ordering is equal to the lexicographic ordering with respect to their complete IDs. In order to make the process as fast as possible, the length of the substring should be minimal. Can you help Georgina to solve this problem?

Input

The input consists of:

  • One line with two integers $n$ and $\ell $, where

    • $n$ ($2 \leq n \leq 500$) is the number of student IDs;

    • $\ell $ ($1 \leq \ell \leq 2 \cdot 10^4$) is the length of each student ID.

  • $n$ lines, the $i$th of which contains the student ID of the $i$th student.

All student IDs only contain lowercase letters of the English alphabet, they are pairwise distinct and appear in ascending lexicographic order.

Output

Output two integers denoting the indices of the first and last letter of the shortest substring so that when students sort themselves lexicographically with respect to this substring of their student ID, the same order establishes as if students sorted themselves lexicographically with respect to their complete student ID.

If there are multiple shortest substrings, you may output any one of them.

Sample Input 1 Sample Output 1
4 6
aaaaaa
aaabbb
aaacaa
aaacac
4 6
Sample Input 2 Sample Output 2
3 5
cccca
ccgda
ccgia
4 4
CPU Time limit 4 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in