ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Open Cup

Time limit: 2.0 second
Memory limit: 256 MB
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.

Input

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 · 105.

Output

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.

Sample

inputoutput
6
mit_kotiki+
sjtu_koty+
itmo_first
msu_koshki
mipt_alot
spsu_kot
0 0
2 2
4 4
5 6
4 6
-1 -1
Problem Author: Mikhail Rubinchik, prepared by Alexander Kulkov
To submit the solution for this problem go to the Problem set: 2131. Open Cup