Les règles de ce jeu peuvent différer légèrement du jeu officiel.
Karen et ses amis participent à un championnat de jeux de société à enjeux élevés, jouant au jeu populaire Codenames. Codenames est un jeu opposant deux équipes : l'équipe rouge et l'équipe bleue. Karen est membre de l'équipe rouge.
Le jeu se joue sur un plateau de taille $5 \times 5$ où chacune des 25 cases est (secrètement) assignée à l'un des quatre types suivants. Il y a un nombre fixe de cases de chaque type sur le plateau :
- 9 cases rouges (r) ;
- 8 cases bleues (b) ;
- 7 cases neutres (n) ;
- 1 case assassin (x).
Les types réels des cases ne sont connus que d'un seul joueur de chaque équipe (appelé le « maître espion »). Les autres joueurs ne voient initialement qu'une grille $5 \times 5$ remplie de cases couvertes. Les cases sont révélées au fur et à mesure que la partie progresse. Chaque case couverte contient le nom d'un objet (ce qui s'avère sans importance pour ce problème).
Heureusement, Karen est le maître espion de son équipe, elle connaît donc la configuration réelle du plateau. Sa responsabilité est d'aider ses coéquipiers à découvrir les cases rouges, tout en les tenant à l'écart de toutes les autres cases (en particulier la case assassin). La façon dont elle peut le faire est d'annoncer un indice composé de :
- un mot valide $w$ (issu d'un dictionnaire de $n$ mots) ;
- un nombre positif $g$ (le nombre de tentatives que ses coéquipiers doivent effectuer).
Ses coéquipiers essaieront ensuite de deviner autant de cases rouges que possible, étant donné l'indice. Ils commencent par faire une première tentative et révèlent l'une des cases. Si la case révélée est rouge, ils peuvent continuer à deviner ; sinon, leur tour s'arrête et l'autre équipe commence son tour. Une équipe gagne la partie si toutes les cases de sa couleur correspondante sont révélées, ou si l'autre équipe a révélé la case assassin.
Pour illustrer cela, considérons l'état du jeu ci-dessous (celui correspondant à l'exemple). L'image de gauche montre la vue du plateau de Karen. L'image du milieu montre la vue du plateau de ses coéquipiers. Notez que certaines cases sont couvertes pour les coéquipiers de Karen, et seule Karen connaît leurs vrais types. La signification de l'image de droite sera expliquée plus loin dans l'énoncé.
À l'origine, le but de Karen était de donner des indices liés aux noms des objets décrits dans certaines des cases rouges, afin que les coéquipiers sachent ne révéler que ces cases. Cependant, elle a vite réalisé que la partie ne se déroulait pas très bien et que l'équipe bleue pourrait les battre à leur prochain tour. Heureusement, elle et ses amis ont conçu un « système de triche d'urgence » secret pour ces situations spécifiques.
Ils commencent par assigner une lettre à chacune des 25 cases, dans l'ordre de lecture (comme illustré ci-dessus, dans l'image de droite). Ensuite, lorsque Karen annonce un mot $w$ et un nombre $g$, ses coéquipiers font ce qui suit :
- Parcourent chacune des lettres $w_i$ du mot $w$ dans l'ordre ;
- Si $w_i$ n'est assignée à aucune case ou si la case assignée à $w_i$ est déjà révélée, alors ils ne font rien ; sinon, ils devinent la case correspondant à $w_i$.
Les coéquipiers répètent cette procédure jusqu'à ce qu'ils révèlent toutes les cases correctes, qu'ils fassent une erreur (révèlent une case non rouge), qu'ils aient déjà effectué les $g$ tentatives, ou que toutes les lettres de $w$ aient été traitées.
Dans l'exemple ci-dessus, Karen pourrait annoncer « actor 2 » à son équipe. Son équipe devinerait d'abord la case (1, 1) (correspondant à la lettre a), ignorerait la lettre c car la case (1, 3) est déjà révélée, puis devinerait la case (4, 5), remportant ainsi la partie (car les autres cases rouges sont déjà révélées).
Karen veut utiliser ce système pour gagner la partie en un seul tour. Elle connaît le dictionnaire de tous les $n$ mots valides, ainsi que l'état actuel du jeu. Trouvez un indice qu'elle devrait annoncer à son équipe pour leur offrir la victoire !
Il y a $q$ scénarios différents que vous devez résoudre. Le dictionnaire est le même pour tous les scénarios, mais les configurations du plateau peuvent différer.
Entrée
La première ligne de l'entrée contient un entier positif $n$ ($1 \le n \le 100\,000$), le nombre de mots valides. Chacune des $n$ lignes suivantes contient une chaîne de caractères d'au moins une et au plus 30 lettres, représentant les mots du dictionnaire.
La ligne suivante contient un entier positif $q$ ($1 \le q \le 100\,000$), le nombre de scénarios. Ensuite, $q$ lignes suivent, chacune décrivant un plateau. Chaque plateau est représenté par une grille $5 \times 5$ de lettres de l'ensemble {r, b, n, x} (rouge/bleu/neutre/assassin). Si la lettre est en majuscule, cela signifie que la case est déjà révélée (sinon la case est couverte). Il y a au moins une case bleue et une case rouge couvertes, et la case assassin est toujours couverte ; en d'autres termes, l'état indique toujours une partie qui n'est pas encore terminée.
Sortie
Pour chacun des $q$ scénarios, affichez l'indice composé d'un mot $w$ et d'un nombre $g$ ($1 \le g \le 9$) qui donne la victoire à l'équipe de Karen. Si aucun indice de ce type ne peut être annoncé pour le scénario spécifique, imprimez un seul mot « IMPOSSIBLE » (sans les guillemets) au lieu de l'indice. Si plusieurs solutions existent, n'importe laquelle est acceptée. Les réponses pour les différents scénarios doivent être imprimées sur des lignes séparées.
Exemples
Entrée 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
Sortie 1
actor 2
Remarque
Notez que Karen n'aurait pas pu annoncer, par exemple, cheat 3, car son équipe finirait par révéler la case à la position (2, 3) et terminerait son tour. D'autres solutions correctes seraient zeta 2 ou actor 4.