Эндрю — тренер по спортивному программированию. Прямо сейчас идёт этап Открытого Кубка по программированию, и Эндрю интересны результаты тех команд, которые он тренирует.

В его любимом браузере есть функция поиска текста на странице: Эндрю вводит некоторую строку, и браузер показывает все её вхождения. Эндрю хочет воспользоваться этим функционалом, чтобы смотреть результаты своих команд. Для этого ему нужно выбрать строку, которая входит во все названия его команд и не входит в название ни одной другой команды.

Но таблица текущих результатов Открытого Кубка устроена так, что команда начинает отображаться в ней только в тот момент, когда впервые отправляет решение на проверку. Изначально таблица пуста. Это означает, что при появлении в таблице результатов каждой новой команды Эндрю, возможно, потребуется обновить строку поиска. Среди всех команд Эндрю есть одна любимая, которая, к счастью для него, сделала первую попытку на соревновании. Так что даже в таблице результатов из одной команды Эндрю есть, за кого болеть.

Найдите строку, по которой должен искать Эндрю после каждой появляющейся в таблице команды.

В первой строке записано целое число n — общее число команд, которые отправляли свои решения на проверку. Далее в n строках перечислены названия этих команд в том порядке, в котором они появлялись в таблице результатов. Названия команд попарно различны и состоят только из строчных латинских букв и символов подчёркивания «_». После названия тех команд, которые тренирует Эндрю, добавлен символ «+». Суммарная длина всех названий не превосходит 2 · 10⁵.

После появления в таблице результатов каждой из команд найдите общую подстроку названий команд Эндрю, не содержащуюся в названиях других команд (учитываются лишь те команды, который в этот момент присутствуют в таблице результатов). Если подходящей строки не существует, нужно выдать «-1 -1». В противном случае нужно вывести целые числа l и r такие, что искомая строка входит в название любимой команды Эндрю с позиции l по позицию r (считая позиции с нуля). Если подходящих строк несколько, выведите самую короткую из них, а если и таких несколько, то ту, для которой минимально значение l.