465. Анализ данных

Не решаласьЛёгкая

Компания «Фриднекс» — молодой стартап, который разрабатывает новую программу для анализа данных и создаёт стартовую базу данных к ней. В программу периодически приходят запросы двух типов:

  • +countword+ \thinspace count \thinspace word

    — это значит, что в базу следует добавить информацию о том, что wordword вводилось ещё countcount раз. На этот запрос программа ничего не отвечает.

  • ?prefix? \thinspace prefix

    — на этот запрос программа должна выбрать слово, которое встречается чаще всего и имеет префикс prefixprefix. Если таких слов несколько, из них нужно выбрать лексикографически минимальное.

Формат ввода

В первой строке находится единственное число n104n \le 10^4 — количество запросов, которые поступят в программу. В следующих nn строках следуют запросы:

  • +countword+ \thinspace count \thinspace word

    — если это первый запрос, где (1count1041 \le count \le 10^4) и (word100|word| \le 100);

  • ?prefix? \thinspace prefix

    — если это второй запрос.

Гарантируется, что запросов второго типа не больше 200200.

Слова состоят только из строчных английских букв.

Формат вывода

Для каждого запроса второго типа выведите единственное слово — ответ на запрос. Если слова с таким префиксом не существует, выведите сам префикс.

Для запросов первого типа выводить что-либо не требуется.

Ограничения

Ограничение времени

3 с

Ограничение памяти

64 МБ

Пример 1

Ввод
8
+ 10 abacaba
? a
+ 11 aba
? a
+ 1 abacaba
? a
+ 1 abacaba
? a
Вывод
abacaba
aba
aba
abacaba

Теги

Нужно войти, чтобы отправить решение.Войти