Base de datos basada en prefijos
Comienzas con una base de datos vacía y necesitas procesar una serie de consultas. Hay dos tipos de consultas: "Add (Agregar)" y "Search (Buscar)". La consulta "Add" agrega un nombre a la base de datos, mientras que la consulta "Search" te pide que muestres todos los nombres de la base de datos que empiecen con un prefijo específico, en orden lexicográfico. Sin embargo, si hay más de 20 nombres que coinciden con ese prefijo, solo debes mostrar los primeros 20.
Entrada
La entrada comienza con un número entero
q (1 ≤ q ≤ 200 000) en la primera línea, que representa la cantidad de consultas. Las siguientes q líneas contienen las consultas en el siguiente formato:- Para las consultas de tipo "Add (Agregar)":
add s(dondeses el nombre que se añade a la base de datos).
- Para las consultas de tipo "Search (Buscar)":
search p(dondepes el prefijo que se busca).
La longitud de las cadenas de las consultas no excede los 20 caracteres.
Salida
Para cada consulta "Search (Buscar)", muestra los nombres de la base de datos que comienzan con el prefijo especificado, separados por un espacio. Si hay más de 20 nombres que coinciden con el prefijo, muestra únicamente los primeros 20.
Ejemplos
Entrada | Salida |
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