База данных на основе префиксов
Изначально у вас есть пустая база данных, и ваша задача — обрабатывать последовательность запросов. Существует два типа запросов: "Add" и "Search". Запрос "Add" добавляет имя в базу, а запрос "Search" требует вывести все имена в базе, которые начинаются с заданного префикса, в лексикографическом порядке. Однако если найденных имен больше 20, нужно вывести только первые 20.
Входные данные
Первая строка содержит целое число
q (1 ≤ q ≤ 200 000), которое задает количество запросов. Следующие q строк описывают запросы в следующем формате:- Для запросов "Add":
add s(гдеs— это имя, которое нужно добавить в базу).
- Для запросов "Search":
search p(гдеp— это префикс, по которому ведется поиск).
Длина строк в запросах не превышает 20 символов.
Выходные данные
Для каждого запроса "Search" выведите имена из базы данных, которые начинаются с запрошенного префикса, разделяя их пробелами. Если подходящих имен больше 20, то выведите только первые 20.
Примеры
Входные данные | Выходные данные |
9
add cat
add code
add core
search co
add profound
add found
search fo
add fight
search f | code
core
found
fight
found |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB