Andrew is a coach of the sport programming. Right now the Open Cup contest is in progress, and Andrew is interested in the results of the teams he trains.

In his favorite browser there is a function of the text search on the page: Andrew enters some string, and the browser shows all of its occurrences. Andrew wants to use this functionality to watch the results of his teams. To do this, he needs to select a string that occurs in all the names of his teams and doesn't occur in a name of any other team.

But the table of the Open Cup current results is arranged in such a way that the team starts to be displayed in it only at the moment when team makes its first submit. Initially the table is empty. This means that when the results of each new Andrew’s team appear in the results table, he may need to update the search string. Among all Andrew’s teams there is one favorite, which, fortunately for him, made the first submit at the competition. So even in the results table with this one team Andrew has someone to cheer for.

After every team that appears in the table find the string that Andrew should look for.

The first line contains an integer n that is the total number of the teams that submitted their solutions. Then in n lines there are the names of these teams in the order they appeared in the results table. The names of the teams are pairwise different and consist only of lowercase latin letters and underscore characters “_”. After the names of those teams, to whom Andrew is a coach, the “+” character is added. The total length of all the names does not exceed 2 · 10⁵.

After the results of each of the teams appear in the table, find the common substring for the names of Andrew’s teams which doesn't occur in the names of the other teams in the results table. If a suitable string doesn't exist, output “-1 -1”. Otherwise, output integers l and r such that the search string occurs in the name of Andrew's favorite team from the index l to the index r (using zero-indexing). If there are several suitable strings, output the shortest of them, and if again there are several of them, output the string for which the index l is minimal.