ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Лучше поздно, чем никогда

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Открытый Кубок

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Эндрю — тренер по спортивному программированию. Прямо сейчас идёт этап Открытого Кубка по программированию, и Эндрю интересны результаты тех команд, которые он тренирует.
В его любимом браузере есть функция поиска текста на странице: Эндрю вводит некоторую строку, и браузер показывает все её вхождения. Эндрю хочет воспользоваться этим функционалом, чтобы смотреть результаты своих команд. Для этого ему нужно выбрать строку, которая входит во все названия его команд и не входит в название ни одной другой команды.
Но таблица текущих результатов Открытого Кубка устроена так, что команда начинает отображаться в ней только в тот момент, когда впервые отправляет решение на проверку. Изначально таблица пуста. Это означает, что при появлении в таблице результатов каждой новой команды Эндрю, возможно, потребуется обновить строку поиска. Среди всех команд Эндрю есть одна любимая, которая, к счастью для него, сделала первую попытку на соревновании. Так что даже в таблице результатов из одной команды Эндрю есть, за кого болеть.
Найдите строку, по которой должен искать Эндрю после каждой появляющейся в таблице команды.

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
6
mit_kotiki+
sjtu_koty+
itmo_first
msu_koshki
mipt_alot
spbsu_kot
0 0
2 2
4 4
5 6
4 6
-1 -1
Автор задачи: Михаил Рубинчик, подготовка — Александр Кульков
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2131. Открытый Кубок