Кодові імена

Правила цієї гри можуть дещо відрізнятися від офіційних.

Карен і її друзі беруть участь у чемпіонаті з настільних ігор з високими ставками, граючи в популярну гру Codenames. Codenames — це гра з двома командами: червоною і синьою. Карен — член червоної команди.

Гра проходить на дошці розміром 5 \times 5, де кожній з $25$ клітинок (таємно) призначено один з чотирьох типів. На дошці є фіксована кількість клітинок кожного типу:

• $9$ червоних клітинок (r);

• $8$ синіх клітинок (b);

• $7$ нейтральних клітинок (n);

• $1$ клітинка-вбивця (x).

Справжні типи клітинок відомі лише одному гравцю з кожної команди (так званому "шпигуну"). Решта гравців спочатку бачать лише сітку 5 \times 5 з повністю закритими клітинками. Клітинки відкриваються в міру гри. Кожна закрита клітинка містить ім'я об'єкта (яке, як виявилося, не має відношення до цього завдання).

На щастя, Карен — шпигун у своїй команді, тому вона знає справжню конфігурацію дошки. Її завдання — допомогти своїм товаришам по команді виявити червоні клітинки, утримуючи їх подалі від усіх інших клітинок (особливо клітинки-вбивці). Вона може зробити це, оголосивши підказку, що складається з:

• допустимого слова $w$ (з словника $n$ слів);

• додатного числа $g$ (кількість здогадок, які повинні зробити її товариші по команді).

Після цього її товариші по команді намагатимуться вгадати якомога більше червоних клітинок, враховуючи підказку. Вони починають з першого припущення і відкривають одну з клітинок. Якщо виявлена клітинка червона, вони можуть продовжити процес вгадування; в іншому випадку їх хід зупиняється, і ходити починає інша команда. Команда виграє гру, якщо розкриваються всі клітинки відповідного кольору, або якщо інша команда відкрила клітинку-вбивцю.

Щоб проілюструвати це, розглянемо стан гри нижче (відповідний прикладу). На лівому зображенні показано, як Карен бачить дошку. На середньому малюнку показано, як її товариші по команді бачать дошку. Зверніть увагу, що деякі з клітинок закриті для товаришів по команді Карен, і тільки Карен знає їх справжні типи. Значення правого зображення буде пояснено пізніше в умові.

Первісно мета Карен полягала в тому, щоб давати підказки, що стосуються назв об'єктів у деяких червоних клітинках, щоб товариші по команді знали, що потрібно відкривати тільки ці клітинки. Однак незабаром вона зрозуміла, що гра йде не дуже добре, і що синя команда може обіграти їх на наступному ході. На щастя, вона і її друзі розробили секретну "схему екстреного шахрайства" спеціально для цих ситуацій.

Вони починають з присвоєння літери кожній з $25$ клітинок у порядку зростання рядків (як показано вище на правому малюнку). Потім, коли Карен вимовляє слово $w$ і число $g$, її товариші по команді будуть робити наступне:

1. Переглянуть кожну з літер w_i слова $w$ по порядку;

2. Якщо w_i не присвоєна жодній клітинці або вказана клітинка w_i вже виявлена, то нічого не робити; в іншому випадку вгадати клітинку, відповідну w_i.

Товариші по команді повторюють цю процедуру доти, поки не відкриють всі правильні клітинки, або зроблять помилку (покажуть не червону клітинку), або вони вже зробили всі $g$ здогадок або всі літери $w$ вже виявлені.

У наведеному вище прикладі Карен може оголосити своїй команді "actor 2". Її команда спочатку вгадує клітинку ($1$, $1$) (відповідає літері a), пропустить літеру c як вже відкриту клітинку ($1$, $3$), потім вгадає клітинку ($4$, $5$) і виграє гру (оскільки інші червоні клітинки вже виявлені).

Карен хоче використати цю схему, щоб виграти гру за один хід. Вона знає словник всіх $n$ допустимих слів, а також поточний стан гри. Знайдіть підказку, яку вона повинна оголосити своїй команді, щоб подарувати їм перемогу!

Є $q$ різних сценаріїв, які Вам потрібно вирішити. Словник однаковий для всіх сценаріїв, але конфігурації дошки можуть відрізнятися.