I - T9

Jakiś czas temu napisanie sms-a było dość niewygodne. Wynikało to z tego, że na komórce dostępne jest tylko dziewięć cyfr, a alfabet ma więcej niż dziewięć liter. Większość liter mogła być wprowadzona tylko przez naciśnięcie określonego przycisku pewną ilość razy. Na przykład, do wpisania "hello" należało wcisnąć przycisk 4 dwa razy, przycisk 3 dwa razy, przycisk 5 trzy razy, jeszcze raz przycisk 5 trzy razy i przycisk 6 trzy razy. Ta procedura jest bardzo żmudna i odstrasza ludzi od pisania sms-ów.
Skłoniło to producentów telefonów komórkowych do znalezienia prostszego sposobu pisania sms-ów. Rozwiązanie zostało nazwane T9. Dziewiątka w nazwie oznacza, że można wprowadzić prawie każde, dowolne słowo używając tylko dziewięciu przycisków i nie wciskając ich więcej niż jeden raz na znak. Pomysł polega na wprowadzaniu kolejno znaków bez powtarzania, a program przejrzy wbudowany słownik w poszukiwaniu najbardziej prawdopodobnego, pasującego wyrazu. Na przykład, żeby wprowadzić "hello" wystarczy nacisnąć po kolei przyciski 4, 3, 5, 5 i 6. Oczywiście mogłoby być to także słowo "gdjjm", ale nie jest to sensowny wyraz, więc zostaje bezpiecznie zignorowany. Przez wyeliminowanie mało prawdopodobnych wyrazów ta metoda może znacząco przyspieszyć pisanie sms-ów, Oczywiście, jeżeli słowa nie ma w słowniku, to musi zostać wprowadzone ręcznie, z powtarzaniem przycisków.

Rys. 1 Klawiatura telefonu komórkowego.

Zadanie

Napisz implementacje słownika T9, która po każdym klawiszu zaproponuje najbardziej prawdopodobną kombinację znaków. Prawdopodobieństwo kombinacji znaków jest zdefiniowane jako suma prawdopodobieństwo wszystkich słów w słowniku, które rozpoczynają się od tej kombinacji. Na przykład, jeżeli w słowniku są słowa "hell", "hello" i "hellfire", to prawdopodobieństwo kombinacji "hell" jest równe sumie prawdopodobieństw tych trzech wyrazów. Jeżeli dwie kombinacje mają takie samo prawdopodobieństwo, to należy wybrać pierwsze w porządku alfabetycznym. Użytkownik powinien mieć także możliwość wpisania prefiksów słów, tzn. jeżeli w słowniku jest słowo "hello" to poprzez wciśnięcie klawiszy 4 i 3 może wprowadzić słowo "he", nawet jeżeli nie ma takiego słowa w słowniku.

Wejście

W pierwszej linii podana jest liczba testów. Każdy test rozpoczyna się liczbą w oznaczającą liczbę słów w słowniku (0 ≤ w ≤ 1000). Słowa są podane w kolejnych w liniach w porządku alfabetycznym. Każde słowo jest ciągiem małych liter alfabetu angielskiego bez białych znaków. Po słowie następuje spacja i liczba całkowita p określająca prawdopodobieństwo wystąpienia danego słowa (1 ≤ p ≤ 100). Żadne słowo nie będzie zawierało więcej niż 100 liter. Po opisie słownika w następnej linii znajduje się liczba całkowita m. W następnych m liniach podane są ciągi co najwyżej 100 cyfr od 2 do 9 zakończone pojedynczą cyfrą 1 oznaczająca następny ciąg.

Wyjście

Dla każdego z m ciągów cyfr oznaczających wprowadzane cyfry wypisz osobną linię dla każdego naciśnięcia przycisku, oprócz ostatniego - cyfry 1. W każdej z tych linii wypisz najbardziej prawdopodobną kombinację znaków wynikającą z dotychczasowo wciśniętych klawiszy zgodnie z zasadami słownika T9. Jeżeli żadne słowo ze słownika nie pasuje do wprowadzonej kombinacji klawiszy wypisz wyraz "RECZNIE" zamiast prefiksu. Po każdym przerobionym ciągu wciśniętych klawiszy wypisz pustą linię. Wypisz dodatkową pustą linię po przerobieniu każdego testu.

Przykładowe wejście

Przykładowe wyjście