- Описание
- Отправленные решения
465. Анализ данных
Компания «Фриднекс» — молодой стартап, который разрабатывает новую программу для анализа данных и создаёт стартовую базу данных к ней. В программу периодически приходят запросы двух типов:
— это значит, что в базу следует добавить информацию о том, что вводилось ещё раз. На этот запрос программа ничего не отвечает.
— на этот запрос программа должна выбрать слово, которое встречается чаще всего и имеет префикс . Если таких слов несколько, из них нужно выбрать лексикографически минимальное.
Формат ввода
В первой строке находится единственное число — количество запросов, которые поступят в программу. В следующих строках следуют запросы:
— если это первый запрос, где () и ();
— если это второй запрос.
Гарантируется, что запросов второго типа не больше .
Слова состоят только из строчных английских букв.
Формат вывода
Для каждого запроса второго типа выведите единственное слово — ответ на запрос. Если слова с таким префиксом не существует, выведите сам префикс.
Для запросов первого типа выводить что-либо не требуется.
Ограничения
Ограничение времени
3 с
Ограничение памяти
64 МБ
Пример 1
8
+ 10 abacaba
? a
+ 11 aba
? a
+ 1 abacaba
? a
+ 1 abacaba
? a
abacaba
aba
aba
abacaba