Comet OJ

C1848 [Contest #13]龙颈之玉-五色的弹丸

内存限制：256 MB 时间限制：1000 ms

题目描述

Gromah 最近沉迷于一款叫做 “贪吃蛇大作战” 的游戏。

给定一个 $n\times m$ 的地图，其中有些格子是空的，有些格子上有食物。初始时贪吃蛇的头在地图中的某个格子上，且贪吃蛇初始只有一个头，每次 Gromah 会控制贪吃蛇的头朝着上下左右四个方向中的一个方向移动一个单位，如果贪吃蛇的头撞到了墙（即坐标不在 $(1,1) - (n,m)$ 范围内），则其立即死亡，否则如果贪吃蛇的头所到达的格子上有一个食物，则贪吃蛇会吃掉这个食物，然后身体立即增加 $1$ 的长度，当然一个食物被吃掉之后就会消失。

具体地，每当进行一次移动，如果没有吃掉一个食物，则贪吃蛇在头部按照给定方向进行移动的同时，身体的每一段也朝着前一段身体的方向进行移动；如果吃掉了一个食物，则只有头部进行移动，原来身体不进行移动，原来的头部位置长出一个单位的身体，即贪吃蛇的身体增加 1 的长度。

特别地，贪吃蛇的头可以和自己的身体重合（起码游戏里是这样子的），保证贪吃蛇的初始位置上不存在食物。

现给定地图，贪吃蛇的头的初始位置，移动序列。如果贪吃蛇中途撞到了墙，则输出GG，否则如果贪吃蛇最后还活着，输出地图的最后状态，具体请见输出格式及样例输出。

输入格式

第一行两个整数 $n,m~(1\le n,m \le 400)$，表示地图大小。

接下来 $n$ 行，每行一个长为 $m$ 的只包含'.','o'和'@'的字符串 $s$，表示地图。其中'.'表示没有食物，'o'表示有一个食物，'@'表示贪吃蛇的头的初始位置。

接下来一行一个只包含'W','A','S','D'的字符串 $t~(1 \le |t| \le 10^5)$，表示操作序列，其中'W'表示向上，'A'表示向左，'S'表示向下，'D'表示向右。

保证地图中有且仅有一个'@'。

输出

如果贪吃蛇中道崩殂，输出GG，否则输出 $n$ 行，每行一个长为 $m$ 的字符串，表示地图的最后状态。其中用'.'表示空地，'o'表示有一个食物，'@'表示贪吃蛇的头，'X'表示贪吃蛇的身体。

特别地，如果贪吃蛇的头与身体重合，在相应格子输出'@'，见样例 $1$。

样例

样例输入 1

4 5
.oo..
.o@.o
..o..
.oo..
WASDSSAD

样例输出 1

.X...
.XX.o
..X..
.X@..

样例输入 2

4 5
.oo..
.o@.o
..o..
.oo..
WASDSSADDDWWWDA

样例输出 2

GG

样例输入 3

1 2
@.
D

样例输出 3

.@

提示