Abfragen zum längsten gemeinsamen Suffix
(Rap battle)
Sie haben eine Liste von
n verschiedenen Wörtern: , sowie eine Liste von q Abfragewörtern . Ihre Aufgabe besteht darin, aus der Liste a das lexikografisch kleinste Wort zu bestimmen, das sich von w unterscheidet und den längsten gemeinsamen Suffix mit w aufweist.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (2 ≤ n ≤ 25 000), die die Anzahl der Zeichenketten in der Liste angibt.In den folgenden
n Zeilen stehen die Zeichenketten. Jede Zeichenkette besteht aus Kleinbuchstaben des englischen Alphabets und ist höchstens 30 Zeichen lang.Die nächste Zeile enthält eine einzelne ganze Zahl
q (1 ≤ q ≤ 25000), die die Anzahl der Abfragezeichenketten angibt.In den folgenden
q Zeilen stehen die Abfragezeichenketten.Jede Zeichenkette besteht aus Kleinbuchstaben des englischen Alphabets und ist höchstens 30 Zeichen lang.
Ausgabe
Für jede Abfrage soll in einer eigenen Zeile das lexikografisch kleinste Wort aus der Liste ausgegeben werden, das sich vom Abfragewort unterscheidet und den längsten gemeinsamen Suffix mit diesem aufweist.
Beispiele
Eingabe | Ausgabe |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB