Wstęp do programowania w C++

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 S₁ i S₂ są wyrazami zapisanymi w A i k jest numerem pierwszego znaku na którym różnią się S₁ i S₂, to S₁ jest leksykograficznie mniejsze niż S₂, jeśli k-ty znak w S₁ występuje w A wcześniej niż k-ty znak z S₂ lub k-1 znak słowa S₁ 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