大蟾蜍设计了一个控制台下的贪吃蛇游戏。贪吃蛇在一个n行*m列的矩形地图内游行，为了防止贪吃蛇游到地图外，n行*m列的地图外一圈都被’#’字符围了起来。

贪吃蛇的食物会随机出现在这个地图的fx行fy列的位置上，用字符’o’表示。

贪吃蛇的身体由k个字符’*’组成，每个字符的位置用(xi,yi)表示。为了能够区分贪吃蛇的头部和尾部，大蟾蜍把贪吃蛇第一个’*’字符替换成’@’字符来代表贪吃蛇的头部。

贪吃蛇可以往 上下左右（分别用字符’w’ ‘s’ ‘a’ ‘d’ 表示）四个方向前进！贪吃蛇前进了w步。贪吃蛇在前进的过程中能不能吃到食物呢（贪吃蛇的头部或身体任一部分覆盖食物就认为吃到了食物）？ 若在前进过程中吃到食物，贪吃蛇立即停止前进，否则走完所有步数后停止。

现给定n、m，fx、fy，并按贪吃蛇从头到尾的顺序给出每个’*’字符的位置xi、yi（其中第一个xi、yi代表贪吃蛇的头部），以及贪吃蛇w步的前进方向，请输出这个矩形地图和吃食物后的贪吃蛇。

输入：

第一行两个正整数n和m。

第二行两个正整数fx和fy。

第三行一个正整数k。

接下来k行，每行两个正整数xi和yi。

再接下来一行，是一个整数w。

接下来w行，每行一个字符，贪吃蛇前进的方向。

输出：

一个被’#’包围的n行*m列的矩形地图，以及前进后的贪吃蛇。（保证贪吃蛇不会撞墙，不会撞自己身体）

输入样例：

4 5

1 5

3

2 1

2 2

3 2

8

s

d

d

d

d

w

w

a

输出样例：

数据规模：

1<=n,m,fx,fy,xi,yi<=30

1<=k,w<=n*m