Wstęp do programowania w C++

Znajdź położenie p słów w danej macierzy liter o wymiarach m na n. Dopasowanie może być wykonane w poziomie, w pionie oraz po przekątnych, w sumie osiem kierunków. Słowo znajduje się w macierzy, gdy kolejne jego litery należą do prostej nieprzerwanej linii pól macierzy. Przy dopasowaniu, wielkość liter nie ma znaczenia.

Input

Dane wejściowe rozpoczynają się od wiersza zawierającego jedną liczbę całkowitą dodatnią, oznaczająca liczbę zestawów danych. Każdy zestaw rozpoczyna się parą liczb całkowitych m i n w wierszu, przy czym 1 <= m, n <= 50. Następnych m wierszy po n liter w każdym reprezentuje macierz, w której należy znaleźć słowa. W macierzy mogą znajdować się małe i wielkie litery. Po opisie macierzy w pliku następuje wiersz z jedną liczbą całkowitą k (1 <= k <= 20). Następnych k wierszy danych wejściowych zawiera listę słów do wyszukania, po jednym słowie w wierszu. Słowa te mogą zawierać jedynie małe i wielkie litery, nie dozwolone są spacje, myślniki i inne znaki spoza alfabetu.

Output

Dla każdego słowa w każdym z zestawów testowych wynikiem powinna być para liczb całkowitych, przedstawiająca jego położenie w odpowiedniej macierzy. Pomiedzy tymi liczbami powinna byc jedna spacja. Pierwsza z liczb mówi o tym, w którym wierszu macierzy znajduje sie pierwsza litera szukanego słowa (1 to najwyższy wiersz, m to wiersz u samego dołu). Druga z tych liczb oznacza kolumnę macierzy, w której znajduje się pierwsza litera szukanego słowa (1 oznacza kolumnę najbardziej na lewo, a n-kolumnę najbardziej na prawo). Jeżeli słowo znajduje się wiecej niż raz w macierzy, wynikiem powinna byc pozycja najwyższego wystąpienia tego słowa w macierzy. Jeżeli najwyższe są dwa lub wiecej słów, wynikiem powinno byc wystapienie najbardziej na lewo. Każde słowo występuje w macierzy co najmniej raz.

Example

Input:
1
8 11
a b c D E F G h i N g
h P b k W a I D S y k
F o i A w a I t O t m
F l s O m r o g s z c
b s o A t m e D e s v
K k c b i R i k o l k
s a r L B G e d h O b
y U i q l x c K B j f
4
Piotrek
Polska
Stomil
Olsztyn

Output:
2 2
2 2
2 9
7 10

Źródło: Wyzwania programistyczne, Steven S. Skiena, Miguel A. Revilla, Tłumaczenie: E. Kieroński, P. Rychlikowski, T. Truderung Edycja naukowa: Profesor L., Polkowski, T. Kaczorek, R. Schaefer, A. Skowron i R. Słowiński, WSiP, 2004