Кодові імена
Правила цієї гри можуть дещо відрізнятися від офіційних.
Карен і її друзі беруть участь у чемпіонаті з настільних ігор з високими ставками, граючи в популярну гру Codenames. Codenames — це гра з двома командами: червоною і синьою. Карен — член червоної команди.
Гра проходить на дошці розміром 5 * 5, де кожній з 25 клітинок (таємно) призначено один з чотирьох типів. На дошці є фіксована кількість клітинок кожного типу:
9 червоних клітинок (r);
8 синіх клітинок (b);
7 нейтральних клітинок (n);
1 клітинка-вбивця (x).
Справжні типи клітинок відомі лише одному гравцю з кожної команди (так званому “шпигуну”). Решта гравців спочатку бачать лише сітку 5 * 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 ≤ n ≤ 10^5) - кількість допустимих слів. Кожен з наступних n рядків містить одне слово з словника. Слова складаються з не менше ніж однієї і не більше ніж 30 літер.
Наступний рядок містить натуральне число q (1 ≤ q ≤ 10^5) - кількість сценаріїв. Потім слідують q рядків, кожен з яких описує дошку. Кожна дошка представлена таблицею 5 * 5 літер з набору {r, b, n, x} (червоний / синій / нейтральний / вбивця). Якщо літера наведена у верхньому регістрі, то відповідна клітинка вже відкрита (в іншому випадку клітинка закрита). У таблиці є принаймні одна синя і одна червона закриті клітинки. Клітинка-вбивця завжди закрита. Іншими словами, стан дошки завжди вказує на те, що гра ще не завершена.
Вихідні дані
Для кожного з q сценаріїв виведіть підказку, що складається з слова w і числа g (1 ≤ g ≤ 9), яка принесе команді Карен перемогу. Якщо в сценарії повідомити таку підказку неможливо, виведіть одне слово “IMPOSSIBLE” (без лапок) замість підказки. Якщо існує декілька рішень, виведіть будь-яке. Відповіді на різні сценарії слід виводити в окремих рядках.
Приклад
Зверніть увагу, що Карен не може оголосити, наприклад, cheat 3, оскільки тоді її команда розкриє клітинку в позиції (2, 3) і закінчить свій хід. Правильними рішеннями будуть zeta 2 або actor 4.