Karen i jej przyjaciele biorą udział w mistrzostwach w popularną grę planszową Codenames. Codenames to gra dla dwóch przeciwnych drużyn: czerwonej i niebieskiej. Karen jest członkinią drużyny czerwonej.
Gra toczy się na planszy o rozmiarze $5 \times 5$, gdzie każdemu z 25 pól przypisany jest (potajemnie) jeden z czterech rodzajów. Na planszy znajduje się ustalona liczba pól każdego rodzaju: 9 pól czerwonych (r); 8 pól niebieskich (b); 7 pól neutralnych (n); 1 pole zabójcy (x).
Prawdziwe rodzaje pól są znane tylko jednemu graczowi z każdej drużyny (zwanemu „mistrzem szpiegów”). Pozostali gracze widzą początkowo tylko siatkę $5 \times 5$ pełną zakrytych pól. Pola są odkrywane w miarę postępu gry. Każde zakryte pole zawiera nazwę obiektu (co okazuje się nieistotne dla tego zadania).
Na szczęście Karen jest mistrzem szpiegów swojej drużyny, więc zna prawdziwą konfigurację planszy. Jej zadaniem jest pomóc kolegom z drużyny odkryć pola czerwone, trzymając ich z dala od wszystkich innych pól (zwłaszcza pola zabójcy). Może to zrobić, ogłaszając wskazówkę składającą się z: poprawnego słowa $w$ (ze słownika $n$ słów); dodatniej liczby $g$ (liczba zgadnięć, które powinni wykonać jej koledzy z drużyny).
Jej koledzy z drużyny spróbują następnie odgadnąć jak najwięcej czerwonych pól, korzystając ze wskazówki. Zaczynają od pierwszego zgadnięcia i odkrywają jedno z pól. Jeśli odkryte pole jest czerwone, mogą zgadywać dalej; w przeciwnym razie ich tura kończy się i zaczyna się tura drugiej drużyny. Drużyna wygrywa grę, jeśli wszystkie pola w jej kolorze zostaną odkryte lub jeśli druga drużyna odkryje pole zabójcy.
Aby to zilustrować, rozważmy stan gry poniżej (odpowiadający przykładowi). Lewy obrazek pokazuje widok planszy Karen. Środkowy obrazek pokazuje widok planszy jej kolegów z drużyny. Zauważ, że niektóre pola są zakryte dla kolegów Karen i tylko ona zna ich prawdziwe rodzaje. Znaczenie prawego obrazka zostanie wyjaśnione w dalszej części zadania.
Początkowo celem Karen było podawanie wskazówek odnoszących się do nazw obiektów opisanych w niektórych czerwonych polach, aby koledzy z drużyny wiedzieli, że mają odkryć tylko te pola. Szybko jednak zdała sobie sprawę, że gra nie idzie najlepiej i że niebieska drużyna może wygrać w swojej następnej turze. Na szczęście ona i jej przyjaciele opracowali specjalnie na takie sytuacje tajny „system oszukiwania w sytuacjach awaryjnych”.
Zaczynają od przypisania litery do każdego z 25 pól, w kolejności wierszowej (jak zilustrowano powyżej, na prawym obrazku). Następnie, gdy Karen ogłasza słowo $w$ i liczbę $g$, jej koledzy z drużyny wykonują następujące czynności:
- Przechodzą przez każdą z liter $w_i$ słowa $w$ w kolejności;
- Jeśli $w_i$ nie jest przypisane do żadnego pola lub przypisane pole dla $w_i$ jest już odkryte, nie robią nic; w przeciwnym razie zgadują pole odpowiadające $w_i$.
Koledzy z drużyny powtarzają tę procedurę, dopóki nie odkryją wszystkich właściwych pól, nie popełnią błędu (odkryją pole niebędące czerwonym), nie wykonają już wszystkich $g$ zgadnięć lub dopóki wszystkie litery $w$ nie zostaną odkryte.
W powyższym przykładzie Karen mogłaby ogłosić „actor 2” swojej drużynie. Jej drużyna najpierw odgadłaby pole (1, 1) (odpowiadające literze a), pominęłaby literę c, ponieważ pole (1, 3) jest już odkryte, a następnie odgadłaby pole (4, 5), wygrywając grę (ponieważ pozostałe czerwone pola są już odkryte).
Karen chce użyć tego schematu, aby wygrać grę w jednej turze. Zna słownik wszystkich $n$ poprawnych słów, a także aktualny stan gry. Znajdź wskazówkę, którą powinna ogłosić swojej drużynie, aby zapewnić im zwycięstwo!
Istnieje $q$ różnych scenariuszy, które musisz rozwiązać. Słownik jest taki sam dla wszystkich scenariuszy, ale konfiguracje planszy mogą się różnić.
Wejście
Pierwsza linia wejścia zawiera liczbę całkowitą dodatnią $n$ ($1 \le n \le 100\,000$), liczbę poprawnych słów. Każda z następujących $n$ linii zawiera pojedynczy ciąg znaków o długości co najmniej jednego i co najwyżej 30 liter, reprezentujący słowa w słowniku.
Następna linia zawiera liczbę całkowitą dodatnią $q$ ($1 \le q \le 100\,000$), liczbę scenariuszy. Następnie następuje $q$ linii, z których każda opisuje planszę. Każda plansza jest reprezentowana przez siatkę $5 \times 5$ liter ze zbioru {r, b, n, x} (czerwony/niebieski/neutralny/zabójca). Jeśli litera jest wielka, oznacza to, że pole jest już odkryte (w przeciwnym razie pole jest zakryte). Istnieje co najmniej jedno niebieskie i jedno czerwone zakryte pole, a pole zabójcy jest zawsze zakryte; innymi słowy, stan zawsze wskazuje na grę, która jeszcze się nie zakończyła.
Wyjście
Dla każdego z $q$ scenariuszy wypisz wskazówkę składającą się ze słowa $w$ i liczby $g$ ($1 \le g \le 9$), która daje drużynie Karen zwycięstwo. Jeśli dla danego scenariusza nie można ogłosić takiej wskazówki, wypisz pojedyncze słowo „IMPOSSIBLE” (bez cudzysłowów) zamiast wskazówki. Jeśli istnieje wiele rozwiązań, każde z nich jest akceptowane. Odpowiedzi dla różnych scenariuszy powinny być wydrukowane w oddzielnych liniach.
Przykład
Wejście 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
Wyjście 1
actor 2
Uwagi
Zauważ, że Karen nie mogłaby ogłosić na przykład cheat 3, ponieważ jej drużyna skończyłaby odkrywając pole na pozycji (2, 3) i kończąc swoją turę. Innymi poprawnymi rozwiązaniami byłyby zeta 2 lub actor 4.
Figure 1. Stan gry: lewy obrazek pokazuje widok planszy Karen, środkowy obrazek pokazuje widok planszy jej kolegów z drużyny, a prawy obrazek ilustruje przypisanie liter do pól.