Lexicographical Lecturing

Time limit2sMemory limit512 MB

Summary

Given n distinct strings already in lexicographic order, find the shortest substring interval [i,j] such that sorting by that substring preserves the same order.

Level: Medium7 of 10
Topics: String, Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

The OUG ("Ordered University of Germany") is a well-known German university. It has a lot of students, so 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.

Examples2

Example 1
Input
```
4 6
aaaaaa
aaabbb
aaacaa
aaacac
```
Expected output
```
4 6
```
Example 2
Input
```
3 5
cccca
ccgda
ccgia
```
Expected output
```
4 4
```