【题目描述】

zzs又开始玩侠盗猎车手5了，这让gta5中的警察xy很头痛。现在zzs操纵人物偷了一辆警车，在洛杉矶市区里飙车。由于这辆警车的跟踪系统十分老旧，它只能发射关于警车移动路线的方向信息。现在已知洛杉矶市区的地图和警车的跟踪记录，xy想在zzs下车以后抓住他。不过她不知道zzs有可能在哪里下车。现在请你告诉她zzs可能的下车位置。

【输入格式】

第一行两个整数n，m。n表示地图的行数，m表示地图的列数。

下面n行，每行m个字符，表示具体的地图。其中点号表示道路，X表示建筑物（也就是不能行车），*表示zzs的偷车位置。

接下来一行，一个整数k，表示警车跟踪记录的方向数。

接下来k行，每行一个单词。EAST，SOUTH，WEST，NORTH分别表示东南西北。地图按上北下南左西右东表示。

【输出格式】

输出一个n*m大小的地图，其中将zzs可能出现的地点用*标识。

【输入样例】

5 5

.....

.XX.X

.....

X..*.

..X.X

4

NORTH

WEST

SOUTH

WEST

【输出样例】

.....

.XX.X

.....

X*...

*.X.X

【数据范围】

对于30%的数据，1<=n，m<=20，1<=k<=20。

对于70%的数据，1<=n，m<=40，1<=k<=500

对于100%的数据，1<=n，m<=50，1<=k<=1000。

【说明】
由于这个行车系统bug多多，警车记录的路线和zzs的开车路线并不完全相同，有些路线可能是假的。有可能出现一些警车直接撞向建筑物的记录情况，直接忽略即可。你只需要按照xy给你的路线来判断就行了。