Правила этой игры могут немного отличаться от официальных.
Карен и её друзья участвуют в чемпионате по настольным играм, играя в популярную игру Codenames. Codenames — это игра с двумя противоборствующими командами: красной и синей. Карен — член красной команды.
Игра проходит на поле размером $5 \times 5$, где каждой из 25 клеток (тайно) присвоен один из четырех типов. На поле фиксированное количество клеток каждого типа: 9 красных клеток (r); 8 синих клеток (b); 7 нейтральных клеток (n); 1 клетка убийцы (x).
Истинные типы клеток известны только одному игроку каждой команды (называемому «шпионом»). Остальные игроки изначально видят только сетку $5 \times 5$, заполненную закрытыми клетками. Клетки открываются по мере развития игры. Каждая закрытая клетка содержит название объекта (что оказывается неважным для этой задачи).
К счастью, Карен — шпион своей команды, поэтому она знает истинную конфигурацию поля. Её обязанность — помочь товарищам по команде открыть красные клетки, избегая при этом всех остальных клеток (особенно клетки убийцы). Она может сделать это, объявив подсказку, состоящую из: допустимого слова $w$ (из словаря, содержащего $n$ слов); положительного числа $g$ (количество догадок, которые должны сделать её товарищи по команде).
Затем её товарищи по команде попытаются угадать как можно больше красных клеток, основываясь на подсказке. Они начинают с первой догадки и открывают одну из клеток. Если открытая клетка красная, они могут продолжать угадывать; в противном случае их ход заканчивается, и начинает ход другая команда. Команда выигрывает игру, если открыты все клетки их цвета или если другая команда открыла клетку убийцы.
Чтобы проиллюстрировать это, рассмотрим состояние игры ниже (соответствующее примеру). На левом рисунке показан вид поля глазами Карен. На среднем рисунке показан вид поля глазами её товарищей по команде. Заметьте, что некоторые клетки закрыты для товарищей Карен, и только Карен знает их истинные типы. Значение правого рисунка будет объяснено далее в условии.
Изначально целью Карен было давать подсказки, относящиеся к названиям объектов, описанных в некоторых красных клетках, чтобы товарищи по команде знали, что нужно открывать только эти клетки. Однако вскоре она поняла, что игра идет не очень хорошо и что синяя команда может победить их в свой следующий ход. К счастью, она и её друзья разработали секретную «схему экстренного жульничества» специально для таких ситуаций.
Они начинают с присвоения буквы каждой из 25 клеток в порядке построчного обхода (как показано выше, на правом рисунке). Затем, когда Карен объявляет слово $w$ и число $g$, её товарищи по команде делают следующее:
- Проходят по каждой из букв $w_i$ слова $w$ по порядку;
- Если $w_i$ не присвоена никакой клетке или присвоенная клетка для $w_i$ уже открыта, то ничего не делают; в противном случае угадывают клетку, соответствующую $w_i$.
Товарищи по команде повторяют эту процедуру, пока не откроют все правильные клетки, не совершат ошибку (откроют не красную клетку), не сделают все $g$ догадок или пока не будут рассмотрены все буквы $w$.
В примере выше Карен могла бы объявить своей команде «actor 2». Её команда сначала угадала бы клетку $(1, 1)$ (соответствующую букве a), пропустила бы букву c, так как клетка $(1, 3)$ уже открыта, а затем угадала бы клетку $(4, 5)$, выиграв игру (так как остальные красные клетки уже открыты).
Карен хочет использовать эту схему, чтобы выиграть игру за один ход. Она знает словарь всех $n$ допустимых слов, а также текущее состояние игры. Найдите подсказку, которую она должна объявить своей команде, чтобы привести их к победе!
Всего нужно решить $q$ различных сценариев. Словарь одинаков для всех сценариев, но конфигурации поля могут различаться.
Входные данные
Первая строка входных данных содержит положительное целое число $n$ ($1 \le n \le 100\,000$), количество допустимых слов. Каждая из следующих $n$ строк содержит одну строку длиной от 1 до 30 букв, представляющую слова в словаре.
Следующая строка содержит положительное целое число $q$ ($1 \le q \le 100\,000$), количество сценариев. Затем следуют $q$ строк, каждая из которых описывает поле. Каждое поле представлено сеткой $5 \times 5$ из букв из набора {r, b, n, x} (красная/синяя/нейтральная/убийца). Если буква заглавная, это означает, что клетка уже открыта (в противном случае клетка закрыта). Есть как минимум одна синяя и одна красная закрытая клетка, а клетка убийцы всегда закрыта; другими словами, состояние всегда указывает на игру, которая еще не завершена.
Выходные данные
Для каждого из $q$ сценариев выведите подсказку, состоящую из слова $w$ и числа $g$ ($1 \le g \le 9$), которая приносит команде Карен победу. Если для конкретного сценария нельзя объявить такую подсказку, выведите одно слово «IMPOSSIBLE» (без кавычек) вместо подсказки. Если существует несколько решений, допускается любое из них. Ответы для разных сценариев должны быть напечатаны на отдельных строках.
Примеры
Примеры 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
actor 2
Примечание
Заметьте, что Карен не могла бы объявить, например, cheat 3, так как её команда в итоге открыла бы клетку в позиции $(2, 3)$ и закончила бы свой ход. Другими правильными решениями могли бы быть zeta 2 или actor 4.