Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PLEXSORT - Sortowanie leksykograficzne

Dany jest alfabet A i lista słów w tym alfabecie. Posortuj słowa według porządku leksykograficznego zgodnego z alfabetem A.

Jeśli S1 i S2 są wyrazami zapisanymi w A i k jest numerem pierwszego znaku na którym różnią się S1 i S2, to S1 jest leksykograficznie mniejsze niż S2, jeśli k-ty znak w S1 występuje w A wcześniej niż k-ty znak z S2 lub k-1 znak słowa S1 jest ostatnim znakiem w tym słowie.

Input

W pierwszej linii liczba testów t, Dla każdego testu w odzielnej linii znaki alfabetu A, który składa się z wybranych małych liter alfabetu łacińskiego. W kolejnej linii n<100 000 - liczba słów. Dalej w każdej linii jedno słowo o długości nie przekraczającej 1 000 liter. Dodatkowo suma liczby liter we wszyskich słowach w każdym z testów nie przekracza 4e6 (4 000 000). Każdy test jest zakończony pustym wierszem.

Output

W kolejnych wierszach posortowane słowa. Po każdym teście jedna linia odstępu.

Example

Input:
2
re
3
ere
rer
re

balujemy
5
bel
luba
lej
bal
leje

Output:
re
rer
ere

bal
bel
luba
lej
leje

Dodane przez:kuszi
Data dodania:2007-03-13
Limit czasu wykonania programu:3s-4s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:C CSHARP C++ 4.3.2 CPP C99 D PAS-GPC PAS-FPC
Pochodzenie:Praktyka Programowania 2007

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.