POLSKI SPOJ

Słyszałeś kiedyś o drzewach binarnych? Jeżeli nie to nie masz się czym przejmować bo od tej pory liczą się tylko drzewa TriTree. W drzewie tym każdy wierzchołek posiada nie dwójkę, lecz trójkę dzieci (z każdego węzła wychodzą krawędzie do trzech innych węzłów). Wyjątek stanowią oczywiście liście czyli węzły bez potomków. Każdy wierzchołek w drzewie TriTree ma przypisaną jedną wielką literę alfabetu angielskiego. Litery mogą się powtarzać na różnych wierzchołkach.

Obecnie jedyną operacją jaką można wykonywać na tego typu drzewie jest wyszukiwanie poprzednika (znajdującego się o P poziomów wyżej) dla wierzchołka o danej literze. W przypadku gdy wyszukiwanie dotyczy litery znajdującej się na kilku węzłach, należy obliczyć poprzednika dla każdego z nich. Węzły z tymi samymi literami obsługujemy w kolejności w jakiej pojawiały się na wejściu (czyli od korzenia w dół i od lewej do prawej strony).

Twoim zadaniem jest zaimplementowanie wyżej opisanej operacji.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 3) określająca ilość zestawów danych. W kolejnych liniach znajduje się Z zestawów danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba naturalna h (1 ≤ h ≤ 12) oznaczająca wysokość drzewa. W kolejnych h wierszach znajdują się opisy węzłów znajdujących się na danym poziomie. Opis i-tego piętra zawiera 3^i-1 liter, są to litery przypisane poszczególnym wierzchołkom. W kolejnej linii znajduje się jedna liczba naturalna q (1 ≤ q ≤ 100) określająca ilość wyszukiwań do wykonania. W kolejnych q liniach znajdują się opisy wyszukiwań. Każdy opis składa się z wielkiej litery alfabetu angielskiego dla której będziemy wyszukiwać poprzednika oraz liczby naturalnej p (1 ≤ p ≤ h-1). Liczba p określa o ile poziomów wyżej od węzła z daną literą ma znajdować się jego poprzednik.

Wyjście

Dla każdego wyszukiwania należy w osobnej linii wypisać litery przypisane do znalezionych poprzedników. W przypadku gdy szukany poprzednik nie istnieje należy wypisać "*". Wypisywane litery należy oddzielić pojedynczą spacją.

Przykład

Wejście:

1
4
A
BCD
EFGHIJKLM
NOPRSTUWABCDEFGHIJKLMNOPRST
10
B 1
B 2
B 3
A 1
A 2
A 3
N 1
O 1
O 2
O 3

Wyjście:

A H
* C
* A
* G
* B
* A
E L
E L
B D
A A