Database basato sui prefissi

All’inizio disponi di un database vuoto e devi gestire una serie di query. Esistono due tipi di query: “Add (aggiungi)” e “Search (cerca)”. La query “Add” aggiunge un nome al database, mentre la query “Search” richiede di mostrare tutti i nomi nel database che iniziano con un determinato prefisso, in ordine lessicografico. Tuttavia, se ci sono più di 20 nomi che corrispondono al prefisso, devi restituire soltanto i primi 20.

Input (Ingresso)

Il primo rigo contiene un intero q (1 ≤ q ≤ 200 000), che rappresenta il numero di query. Le q righe successive contengono le query, con il seguente formato:

• Per le query “Add”: add s (dove s è il nome da aggiungere al database).

• Per le query “Search”: search p (dove p è il prefisso da cercare).

La lunghezza delle stringhe nelle query non supera i 20 caratteri.

Output (Uscita)

Per ogni query “Search”, stampa i nomi del database che iniziano con il prefisso indicato, separati da uno spazio. Se i nomi corrispondenti al prefisso sono più di 20, mostrane soltanto i primi 20.

Esempi