填字游戏

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

有一种填字游戏叫Crossword,如图1所示。它是在一个划分成许多相同的矩形小方格(内有白格和黑格)的棋盘上填单词。填词的规则是:从左到右或从上到下将单词填到白格上。 



 一个across单词是指在某一行中,从最左边或从一个左边是黑格的白格开始向右,直到遇到第一个黑格或最右边的格子为止的单词。

一个clown单词是指在某一列中,从最上边或从一个上边是黑格的白格开始向下,直到遇到第一个黑格或最下边的格子为止的单词。

现已知从一个Crossword棋盘中读出的所有across单词和clown单词,这些单词给出的顺序是任意的,但可知道是across单词还是clown单词。编写一个程序,还原出这个Crossword棋盘。要求从还原的Crossword棋盘中读出的所有across单词和clown单词,和已知的across单词和clown单词完全一致,不能有遗落、多余或重复。若有多个棋盘满足要求,则只需输出其中一个。

Input

输入数据的第一行是两个整数M和N,表示Crossword棋盘的大小是M*N(M行N列,M<=10,N<=10)。

第二行是两个整数A和C,分别表示已知的across单词和clown单词的个数。

接着的A行,每行是一个across单词,across单词之间不会重复。再接着的C行,每行是一个clown单词,clown单词之间不会重复。

Output

用一个M*N(M行N列)的字符矩阵来表示Crossword棋盘。

白格用该格的字母表示,黑格用“*”表示。每列用一个空格隔开。

Sample Input

5 4
5 5
CAR
SUN
NC
POE
EDT
UNDER
EOA
NCT
PC
S

Sample Output

* S U N
* * N C
* E D T
P O E *
C A R *

Hint

Source