このゲームのルールは、公式のゲームとは若干異なる場合があります。
Karenと彼女の友人たちは、高額な賞金をかけたボードゲーム選手権で、人気ゲーム「Codenames」をプレイしています。Codenamesは、赤チームと青チームの2つの対立するチームで行われるゲームです。Karenは赤チームのメンバーです。
ゲームは $5 \times 5$ のボードで行われ、25個の各マスには（秘密裏に）4種類のいずれかが割り当てられています。ボード上の各種類のマスの数は固定されています。
- 9個の赤マス (r)
- 8個の青マス (b)
- 7個の中立マス (n)
- 1個の暗殺者マス (x)
マスの真の種類は、各チームの1人のプレイヤー（「スパイマスター」と呼ばれます）のみが知っています。他のプレイヤーは最初、$5 \times 5$ の覆われたマスで埋め尽くされたグリッドしか見ることができません。マスはゲームの進行とともに明らかになります。覆われた各マスにはオブジェクトの名前が書かれています（これは本問題には関係ありません）。
幸いなことに、Karenはチームのスパイマスターであるため、ボードの真の構成を知っています。彼女の役割は、チームメイトが赤マスを見つけるのを助けつつ、他のすべてのマス（特に暗殺者マス）を避けるように誘導することです。彼女ができることは、以下の要素からなるヒントを出すことです。
- 有効な単語 $w$ （$n$ 個の単語からなる辞書から選択）
- 正の整数 $g$ （チームメイトが行うべき推測の回数）
チームメイトは、ヒントを与えられた後、できるだけ多くの赤マスを推測しようとします。彼らは最初の推測を行い、マスの1つを明らかにします。明らかになったマスが赤であれば、彼らは推測を続けることができます。そうでなければ、彼らのターンは終了し、相手チームのターンが始まります。チームは、自分たちの色のマスがすべて明らかになった場合、または相手チームが暗殺者マスを明らかにした場合に勝利します。
これを説明するために、以下のゲームの状態（例に対応するもの）を考えてみましょう。左の図はKarenから見たボードの状態です。中央の図はチームメイトから見たボードの状態です。チームメイトにとっては一部のマスが覆われており、その真の種類を知っているのはKarenだけであることに注意してください。右の図の意味は、この問題文の後半で説明されます。
もともと、Karenの目標は、赤マスに書かれたオブジェクトの名前に関連するヒントを出し、チームメイトがそれらのマスだけを明らかにするようにすることでした。しかし、彼女はすぐにゲームがうまくいっておらず、次のターンで青チームに負けてしまう可能性があることに気づきました。幸いなことに、彼女と友人たちは、このような状況のために「緊急不正スキーム」を考案しました。
彼らは、右の図に示すように、25個の各マスに、行優先順序で文字を割り当てます。そして、Karenが単語 $w$ と数字 $g$ を発表すると、チームメイトは以下のように行動します。
- 単語 $w$ の各文字 $w_i$ を順番に確認します。
- もし $w_i$ がどのマスにも割り当てられていないか、または $w_i$ に割り当てられたマスがすでに明らかになっている場合は、何もしません。そうでなければ、$w_i$ に対応するマスを推測します。
チームメイトは、正しいマスをすべて明らかにするか、間違いを犯す（赤以外のマスを明らかにする）か、すでに $g$ 回の推測を行ったか、あるいは $w$ のすべての文字を確認し終えるまで、この手順を繰り返します。
上記の例では、Karenはチームに「actor 2」と伝えることができます。チームはまず（文字 a に対応する）マス (1, 1) を推測し、マス (1, 3) はすでに明らかになっているため文字 c をスキップし、次にマス (4, 5) を推測してゲームに勝利します（他の赤マスはすでに明らかになっているため）。
Karenはこのスキームを使って、1ターンでゲームに勝利したいと考えています。彼女は $n$ 個のすべての有効な単語の辞書と、現在のゲームの状態を知っています。チームが勝利するために彼女が発表すべきヒントを見つけてください。
解決すべき異なるシナリオが $q$ 個あります。辞書はすべてのシナリオで共通ですが、ボードの構成は異なる場合があります。
入力
入力の最初の行には、有効な単語の数である正の整数 $n$ ($1 \le n \le 100\,000$) が含まれます。続く $n$ 行の各行には、辞書内の単語を表す、1文字以上30文字以下の文字列が1つ含まれます。
次の行には、シナリオの数である正の整数 $q$ ($1 \le q \le 100\,000$) が含まれます。その後、$q$ 個のシナリオが続き、それぞれがボードを記述しています。各ボードは、集合 {r, b, n, x} （赤/青/中立/暗殺者）の文字からなる $5 \times 5$ のグリッドで表されます。文字が大文字の場合、そのマスはすでに明らかになっていることを意味します（小文字の場合はマスは覆われています）。少なくとも1つの青い覆われたマスと1つの赤い覆われたマスが存在し、暗殺者マスは常に覆われています。言い換えれば、状態は常にゲームがまだ終了していないことを示しています。
出力
各 $q$ 個のシナリオについて、Karenのチームを勝利に導く単語 $w$ と数字 $g$ ($1 \le g \le 9$) からなるヒントを出力してください。特定のシナリオに対してそのようなヒントを出せない場合は、ヒントの代わりに「IMPOSSIBLE」という単語を1つ出力してください。複数の解が存在する場合は、どれを出力しても構いません。異なるシナリオの答えは、別々の行に出力してください。
入出力例
入力 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
出力 1
actor 2
注記
例えば、Karenは「cheat 3」と発表することはできません。なぜなら、チームは最終的に位置 (2, 3) のマスを明らかにしてしまい、ターンが終了してしまうからです。他の正しい解としては「zeta 2」や「actor 4」などがあります。