ISAB - Isabella Message

### 背景 Isabella和Steve是好♂朋♀友,他们经常互通 ~~情书~~ 书信。他们分享愉快的经历,谈论周围的人们,倾述他们的情感...他们在信中分享几乎所有事情。当他们的信送出时,他们特别担心有人后偷看他们的信(特别是他们的父母)。所以他们给信进行了 只有他们知道解密方法的 加密,这就保证了他们的隐私。 ### 题目描述 信息被加密为了一个*N*×*N*(*N*位偶数)的矩阵,矩阵的每一个位置包含一个字符。 Steve用一张特殊的蒙版作为秘钥。 蒙版也是一个*N*×*N*的矩阵,这个矩阵包含*N*×*N*÷4个,大小为1×1的洞。 #### 解密方式如下 1. 将蒙版放在加密信息矩阵上 2. 写下透过洞可以看到的字符,**从上到下,从左到右** 3. 将蒙版**顺时针**旋转**90°** 4. 继续**步骤2**,直到你写下了**所有四个方向的情况**(按顺序将写下内容拼接)(**原意**:直到你写下了每一个信息矩阵中的每一个字符) 5. 去掉你写下信息中**多余的**空格 ###### 举个栗子 你有了一个加密信息(如图1),并且你有了一个秘钥蒙版(如图2)。解密过程如图3展示,最后你会获得一个信息:"good morning"。   你大可假设蒙版是特制的,以解密过程中使每个字符仅出现一次(假设与解密过程原意有关)。 然而,过程的第一步有**多种放置方法**(实际就四种。。。。),因为蒙版可以旋转(**即**四个方向**均**可作为第一步放上信息矩阵)。因此,你可能得到**多个不同的结果**,比如上述例子中,你也可以得到"od morning go"(过程如图4所示),同样的,你也能得到其他答案,如"orning good m"和"ng good morni"。  Steve也不知道正确的解密方式,还好他还有一张**单词表**,而正确信息中只会出现**表上的单词**。当出现**多条满足条件**的信息时,选择**字典序**最小的一条。(此处完全**意译**,原意要长太扯了。。。。。) 当然也有 **没有满足条件的信息** 的情况。 Isabella每天的发信息,而解密工作耗费了Steve大把的精力,Steve总迫不及代,希望立刻看到信息,于是他找到了你帮他构造程序解密 上述的加密信息矩阵,蒙版,单词表以以下方式给出 ### 输入输出格式 #### 输入格式: 第一行为一个整数***T***,指出有***T***个矩阵需要解密。 对于**每一种情况** ***i***: - 第一行给出整数***N*** - 接下来***N***行,每行***N***个字符,描述**加密信息**矩阵(字符'.'表示空格) - 接下来***N***行,每行***N***个字符,描述**秘钥蒙版**矩阵 - 接着一行给出***M***,表示**单词表**单词数 - 接着***M***行，每行给出表中的一个单词 #### 输出格式: 输出共***T***行 对于输入***i***,输出一行"Case #i: S" 其中,***i***为***i***(嗯。。。),S为满足条件的信息 若**没有满足条件的信息**,S为"FAIL TO DECRYPT".

Isabella and Steve are very good friends, and they often write letters to each other. They exchange funny experiences, talk about people around, share their feelings and write about almost everything through the letters. When the letters are delivered, they are quite afraid that some other people(maybe their parents) would peek. So they encrypted the letter, and only they know how to decrypt it. This guarantees their privacy. The encrypted message is an **N**×**N** matrix, and each grid contains a character. Steve uses a special mask to work as a key. The mask is **N**×**N**(where **N** is an even number) matrix with (**N**×**N**)/4 holes of size **1**×**1** on it. The decrypt process consist of the following steps: 1. Put the mask on the encrypted message matrix. 2. Write down the characters you can see through the holes, from top to down, then from left to right. 3. Rotate the mask by 90 degrees clockwise. 4. Go to step 2, unless you have wrote down all the **N**×**N** characters in the message matrix. 5. Erase all the redundant white spaces in the message. For example, you got a message shown in figure 1, and you have a mask looks like figure 2. The decryption process is shown in figure 3, and finally you may get a message "good morning". You can assume that the mask is always carefully chosen that each character in the encrypted message will appear exactly once during decryption. However, in the first step of decryption, there are several ways to put the mask on the message matrix, because the mask can be rotated (but not flipped). So you may get different results such as "od morning go" (as showed in figure 4), and you may also get other messages like "orning good m", "ng good morni". Steve didn't know which direction of the mask should be chosen at the beginning, but after he tried all possibilities, he found that the message "good morning" is the only one he wanted because he couldn't recognize some words in the other messages. So he will always consider the message he can understand the correct one. Whether he can understand a message depends whether he knows all the words in the message. If there are more than one ways to decrypt the message into an understandable one, he will choose the lexicographically smallest one. The way to compare two messages is to compare the words of two messages one by one, and the first pair of different words in the two messages will determine the lexicographic order of them. Isabella sends letters to Steve almost every day. As decrypting Isabella's message takes a lot of time, and Steve can wait no longer to know the content of the message, he asked you for help. Now you are given the message he received, the mask, and the list of words he already knew, can you write a program to help him decrypt it?

The first line contains an integer **T** (1 ≤ **T** ≤ 100), indicating the number of test cases. Each test case contains several lines. The first line contains an even integer **N** (2 ≤ **N** ≤ 50), indicating the size of the matrix. The following **N** lines each contains exactly **N** characters, reresenting the message matrix. The message only contains lowercase letters and periods('.'), where periods represent the white spaces. You can assume the matrix contains at least one letter. The following **N** lines each contains **N** characters, representing the mask matrix. The asterisk('\*') represents a hole, and period('.') otherwise. The next line contains an integer **M**(1 ≤ **M** ≤ 100), the number of words he knew. Then the following **M** lines each contains a string represents a word. The words only contain lowercase letters, and its length will not exceed 20.

For each test case in the input, print one line: "Case #X: Y", where **X** is the test case number (starting with 1) and **Y** is Isabella's message. If Steve cannot understand the message, just print the **Y** as "FAIL TO DECRYPT".

3
4
o.do
.ng.
grmn
o.i.
.*..
*.*.
....
*...
2
good
morning
4
..lf
eoyv
oeou
vrer
..*.
.*..
....
*.*.
5
i
you
the
love
forever
4
.sle
s.c.
e.fs
..uu
*...
.*..
...*
..*.
1
successful

Case #1: good morning
Case #2: love you forever
Case #3: FAIL TO DECRYPT