카렌과 그녀의 친구들은 인기 있는 보드게임인 코드네임(Codenames)을 플레이하며 높은 판돈이 걸린 보드게임 챔피언십에 참가하고 있습니다. 코드네임은 빨간 팀과 파란 팀, 두 팀이 대결하는 게임입니다. 카렌은 빨간 팀의 일원입니다.
게임은 $5 \times 5$ 크기의 보드에서 진행되며, 25개의 각 칸에는 네 가지 종류 중 하나가 (비밀리에) 할당되어 있습니다. 보드에는 각 종류별로 정해진 개수의 칸이 있습니다.
- 9개의 빨간색 칸 (r)
- 8개의 파란색 칸 (b)
- 7개의 중립 칸 (n)
- 1개의 암살자 칸 (x)
각 칸의 실제 종류는 각 팀의 플레이어 중 한 명(스파이마스터라고 함)만 알고 있습니다. 다른 플레이어들은 처음에 덮여 있는 $5 \times 5$ 격자판만 볼 수 있습니다. 게임이 진행됨에 따라 칸들이 공개됩니다. 덮여 있는 각 칸에는 물체의 이름이 적혀 있습니다(이 문제에서는 중요하지 않습니다).
다행히 카렌은 팀의 스파이마스터이므로 보드의 실제 구성을 알고 있습니다. 그녀의 책임은 팀원들이 빨간색 칸을 찾도록 돕는 동시에, 다른 모든 칸(특히 암살자 칸)을 피하도록 하는 것입니다. 그녀는 다음과 같은 힌트를 발표하여 이를 수행할 수 있습니다.
- 유효한 단어 $w$ (사전에 있는 $n$개의 단어 중 하나)
- 양의 정수 $g$ (팀원들이 추측해야 할 횟수)
팀원들은 힌트를 받으면 가능한 한 많은 빨간색 칸을 추측하려고 시도합니다. 그들은 첫 번째 추측을 시작하여 칸 중 하나를 공개합니다. 공개된 칸이 빨간색이면 계속해서 추측할 수 있고, 그렇지 않으면 차례가 끝나고 상대 팀의 차례가 시작됩니다. 한 팀은 자신의 색상에 해당하는 모든 칸이 공개되거나, 상대 팀이 암살자 칸을 공개하면 게임에서 승리합니다.
이를 설명하기 위해 아래의 게임 상태(예제에 해당하는 상태)를 고려해 봅시다. 왼쪽 그림은 카렌이 보는 보드입니다. 가운데 그림은 카렌의 팀원들이 보는 보드입니다. 카렌의 팀원들에게는 일부 칸이 덮여 있으며, 오직 카렌만이 그들의 실제 종류를 알고 있다는 점에 유의하세요. 오른쪽 그림의 의미는 문제 뒷부분에서 설명합니다.
원래 카렌의 목표는 빨간색 칸에 적힌 물체의 이름과 관련된 힌트를 주어 팀원들이 해당 칸만 공개하도록 하는 것이었습니다. 하지만 그녀는 곧 게임이 잘 풀리지 않고 있으며 다음 차례에 파란 팀이 승리할 수도 있다는 것을 깨달았습니다. 다행히 그녀와 친구들은 이러한 상황을 위해 비밀 "긴급 부정행위 계획"을 고안했습니다.
그들은 오른쪽 그림에 나타난 것처럼 25개의 각 칸에 행 우선 순서로 문자를 할당합니다. 그런 다음 카렌이 단어 $w$와 숫자 $g$를 발표하면, 팀원들은 다음과 같이 행동합니다.
- 단어 $w$의 각 문자 $w_i$를 순서대로 확인합니다.
- 만약 $w_i$가 어떤 칸에도 할당되어 있지 않거나 $w_i$에 할당된 칸이 이미 공개된 상태라면 아무것도 하지 않습니다. 그렇지 않으면 $w_i$에 해당하는 칸을 추측합니다.
팀원들은 모든 올바른 칸을 공개하거나, 실수를 하거나(빨간색이 아닌 칸을 공개), 이미 $g$번의 추측을 모두 마쳤거나, 단어 $w$의 모든 문자를 확인했을 때까지 이 과정을 반복합니다.
위의 예시에서 카렌은 팀에게 "actor 2"라는 힌트를 줄 수 있습니다. 팀은 먼저 (문자 a에 해당하는) (1, 1) 칸을 추측하고, (1, 3) 칸은 이미 공개되어 있으므로 문자 c는 건너뛴 뒤, (4, 5) 칸을 추측하여 게임에서 승리하게 됩니다(다른 빨간색 칸들은 이미 공개된 상태이므로).
카렌은 이 계획을 사용하여 한 번의 차례에 게임을 승리하고자 합니다. 그녀는 $n$개의 모든 유효한 단어와 현재 게임 상태를 알고 있습니다. 팀에게 승리를 안겨줄 힌트를 찾아내세요!
해결해야 할 $q$개의 서로 다른 시나리오가 있습니다. 사전은 모든 시나리오에서 동일하지만 보드 구성은 다를 수 있습니다.
입력
첫 번째 줄에는 유효한 단어의 개수인 양의 정수 $n$ ($1 \le n \le 100\,000$)이 주어집니다. 이어지는 $n$개의 줄에는 사전에 있는 단어를 나타내는, 길이가 최소 1 이상 30 이하인 문자열이 하나씩 주어집니다.
다음 줄에는 시나리오의 개수인 양의 정수 $q$ ($1 \le q \le 100\,000$)가 주어집니다. 그 후 $q$개의 줄이 이어지며, 각 줄은 보드를 설명합니다. 각 보드는 $\{r, b, n, x\}$ (빨간색/파란색/중립/암살자) 집합의 문자로 구성된 $5 \times 5$ 격자로 표현됩니다. 문자가 대문자이면 해당 칸이 이미 공개된 상태임을 의미합니다(그렇지 않으면 칸이 덮여 있는 상태입니다). 최소한 하나 이상의 파란색 칸과 빨간색 칸이 덮여 있으며, 암살자 칸은 항상 덮여 있습니다. 즉, 게임 상태는 항상 아직 끝나지 않은 게임을 나타냅니다.
출력
각 $q$개의 시나리오에 대해, 카렌의 팀이 승리할 수 있는 단어 $w$와 숫자 $g$ ($1 \le g \le 9$)로 구성된 힌트를 출력합니다. 특정 시나리오에 대해 그러한 힌트를 발표할 수 없는 경우, 힌트 대신 "IMPOSSIBLE"이라는 단어를 출력합니다. 여러 해답이 존재할 경우 아무거나 하나를 출력해도 됩니다. 서로 다른 시나리오에 대한 답은 별도의 줄에 출력해야 합니다.
예제
입력 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
출력 1
actor 2
참고
카렌은 예를 들어 "cheat 3"과 같은 힌트는 발표할 수 없음에 유의하세요. 팀이 (2, 3) 위치의 칸을 공개하고 차례를 마치게 되기 때문입니다. 다른 올바른 해답으로는 "zeta 2" 또는 "actor 4"가 있습니다.