题目描述

地图中 . 可行车，X 不可行车，唯一的 * 是汽车初始位置。收到一系列方向指令，每条指令表示汽车沿该方向连续行驶一个或更多格，不能经过障碍或越界。求执行全部指令后汽车所有可能的位置。

输入格式

第一行 $R,C$，随后 $R$ 行，每行 $C$ 个地图字符。下一行指令数量 $N$，接下来 $N$ 行分别为 NORTH、SOUTH、WEST、EAST 之一；相邻指令不同。

输出格式

输出 $R$ 行地图：障碍保留为 X，所有最终可能的位置标为 *，其余可行车位置标为 .。

样例

1 4
*...
1
EAST

.***

数据范围

$1\le R,C\le50$，$1\le N\le1000$。