Karen 和她的朋友們正在參加一場高風險的桌遊錦標賽,遊玩熱門遊戲《機密代號》(Codenames)。《機密代號》是一款由兩個對立隊伍進行的遊戲:紅隊與藍隊。Karen 是紅隊的一員。
遊戲在一個 $5 \times 5$ 的棋盤上進行,其中 25 個格子中的每一個都被(秘密地)分配了四種種類之一。棋盤上每種種類的格子數量是固定的:
- 9 個紅色格子 (r);
- 8 個藍色格子 (b);
- 7 個中立格子 (n);
- 1 個刺客格子 (x)。
格子的真實種類只有每個隊伍的一名玩家(稱為「情報員」)知道。其他玩家最初只看到一個充滿覆蓋格子的 $5 \times 5$ 網格。隨著遊戲進行,格子會被揭開。每個被覆蓋的格子都包含一個物體的名稱(這對本題來說並不重要)。
幸運的是,Karen 是她隊伍的情報員,因此她知道棋盤的真實配置。她的職責是幫助隊友找出紅色格子,同時讓他們遠離所有其他格子(特別是刺客格子)。她可以透過發布一個提示來做到這一點,該提示包含:
- 一個有效的單字 $w$(來自一個包含 $n$ 個單字的字典);
- 一個正整數 $g$(隊友應該進行的猜測次數)。
她的隊友隨後會根據提示,嘗試猜測盡可能多的紅色格子。他們從第一次猜測開始,揭開其中一個格子。如果揭開的格子是紅色的,他們可以繼續猜測;否則,他們的回合結束,由另一隊開始他們的回合。如果一個隊伍揭開了所有對應顏色的格子,或者另一隊揭開了刺客格子,該隊伍就贏得遊戲。
為了說明這一點,讓我們考慮下方的遊戲狀態(對應範例的狀態)。左圖顯示了 Karen 眼中的棋盤。中間的圖顯示了她隊友眼中的棋盤。請注意,對於 Karen 的隊友來說,有些格子是被覆蓋的,只有 Karen 知道它們的真實種類。右圖的含義將在後文中解釋。
最初,Karen 的目標是提供與某些紅色格子中描述的物體名稱相關的提示,以便隊友知道只揭開那些格子。然而,她很快意識到遊戲進展並不順利,藍隊可能會在下一回合擊敗他們。值得慶幸的是,她和她的朋友們專門為這些情況設計了一種秘密的「緊急作弊方案」。
他們首先為 25 個格子中的每一個分配一個字母,按列優先順序排列(如上圖右側所示)。然後,當 Karen 發布一個單字 $w$ 和一個數字 $g$ 時,她的隊友會執行以下操作:
- 依序遍歷單字 $w$ 的每個字母 $w_i$;
- 如果 $w_i$ 沒有分配給任何格子,或者 $w_i$ 對應的格子已經被揭開,則什麼都不做;否則,猜測 $w_i$ 對應的格子。
隊友重複此過程,直到他們揭開所有正確的格子、犯了錯誤(揭開非紅色格子)、已經進行了所有 $g$ 次猜測,或者單字 $w$ 的所有字母都已被揭開。
在上面的範例中,Karen 可以向她的隊伍宣布「actor 2」。她的隊伍會先猜測格子 $(1, 1)$(對應字母 a),跳過字母 c(因為格子 $(1, 3)$ 已經被揭開),然後猜測格子 $(4, 5)$,從而贏得遊戲(因為其他紅色格子已經被揭開)。
Karen 希望利用這個方案在一回合內贏得遊戲。她知道所有 $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\}$(紅/藍/中立/刺客)。如果字母是大寫的,則表示該格子已經被揭開(否則該格子是被覆蓋的)。至少有一個藍色和一個紅色的被覆蓋格子,且刺客格子總是處於被覆蓋狀態;換句話說,狀態總是表示遊戲尚未結束。
輸出格式
對於每個場景,輸出一個由單字 $w$ 和數字 $g$ ($1 \le g \le 9$) 組成的提示,使 Karen 的隊伍獲勝。如果對於特定場景無法宣布這樣的提示,則輸出單字 “IMPOSSIBLE”(不含引號)來代替提示。如果存在多個解,則接受其中任何一個。不同場景的答案應列印在不同的行上。
範例
輸入 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
輸出 1
actor 2
說明
請注意,Karen 不能宣布例如 cheat 3,因為她的隊伍最終會揭開位置 $(2, 3)$ 的格子並結束他們的回合。其他一些正確的解法包括 zeta 2 或 actor 4。