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 (donde s es el nombre que se añade a la base de datos).

• Para las consultas de tipo "Search (Buscar)": search p (donde p es 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