Präfixbasierte Datenbank
Am Anfang steht eine leere Datenbank zur Verfügung, in der eine Reihe von Abfragen verarbeitet werden muss. Es gibt zwei Arten von Abfragen: "Add" und "Search". Die Abfrage "Add" fügt einen Namen zur Datenbank hinzu, während die Abfrage "Search" alle Namen ausgibt, die mit einem bestimmten Präfix beginnen – sortiert in lexikografischer Reihenfolge. Sollten mehr als 20 Namen zum gesuchten Präfix passen, sollen nur die ersten 20 ausgegeben werden.
Eingabe
Die Eingabe beginnt mit einer ganzen Zahl
q (1 ≤ q ≤ 200 000), die angibt, wie viele Abfragen folgen. In den nächsten q Zeilen stehen dann die einzelnen Abfragen im folgenden Format:- Für "Add"-Abfragen:
add s(wobei "s" der hinzuzufügende Name ist).
- Für "Search"-Abfragen:
search p(wobei "p" das zu suchende Präfix ist).
Die Länge der Abfragezeichenketten überschreitet dabei nie 20 Zeichen.
Ausgabe
Bei jeder "Search"-Abfrage sollen alle passenden Namen, die mit dem gesuchten Präfix beginnen, in einer Zeile ausgegeben werden, getrennt durch ein Leerzeichen. Falls es mehr als 20 Treffer gibt, werden nur die ersten 20 Namen ausgegeben.
Beispiele
Eingabe | Ausgabe |
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