#P1629. Fillword

Fillword

描述

亚历克斯喜欢玩填字游戏。填字游戏是一种规则非常简单的文字游戏。填字游戏的创作者会使用一个矩形网格(宽度为MM个单元格,高度为NN个单元格)以及PP个单词。然后他会在网格的单元格中写入字母(每个单元格写入一个字母),使得每个单词都能在网格中找到,并且满足以下条件:

  1. 每个单元格最多属于一个单词。
  2. 每个单元格不会被同一个单词使用多次。 对于某个单词WW(假设其长度为kk),如果能找到这样一个单元格序列(x1,y1),(x2,y2),,(xk,yk)(x_1, y_1), (x_2, y_2), \cdots, (x_k, y_k),满足:
  3. 对于每个i=1,2,,k1i = 1, 2, \cdots, k - 1,单元格(xi,yi)(x_i, y_i)(xi+1,yi+1)(x_{i + 1}, y_{i + 1})是相邻的(xixi+1+yiyi+1=1|x_i - x_{i + 1}| + |y_i - y_{i + 1}| = 1)。
  4. 单词WW的第ii个字母写在坐标为(xi,yi)(x_i, y_i)的单元格中。 那么这个单词WW就能在网格中找到。

任务是在网格中找到所有的单词。在找到所有单词后,你会发现网格中有些单元格的字母没有被使用(这些字母不属于任何找到的单词)。用这些字母组成一个秘密单词就能赢得大奖。

为了更清楚地说明,让我们看下面这个例子(单词是“BEG”和“GEE”):

你的任务是帮助亚历克斯完成填字游戏。你应该找出在找到所有单词后剩下的字母。而用这些字母组成秘密单词这个最困难的任务,仍然留给亚历克斯来完成。

输入

输入文件的第一行包含三个整数——NNMM2M,N102 \leq M, N \leq 10)和PPP100P \leq 100)。接下来的NN行,每行包含MM个字符,代表这个网格。再接下来的PP行包含要在填字游戏网格中找到的单词。

填字游戏总是至少有一个解决方案。填字游戏中出现的所有字符都是大写英文字母。

输出

输出组成秘密单词所需的字母。字母应按字典序输出。

输入数据 1

3 3 2
EBG
GEE
EGE
BEG
GEE

输出数据 1

EEG

来源

2001 年东北欧竞赛,北部分区