Problem 1085 --贪吃蛇

1085: 贪吃蛇

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 211  Solved: 42
[Submit][Status][Web Board][Creator:]

Description

贪吃蛇游戏是一款经典的益智游戏,有PC和手机等多平台版本。既简单又耐玩,该游戏通过控制蛇头方向吃蛋,从而使得蛇变得越来越长。撞到屏幕四周或者自己的身体,蛇就会死亡。

Alice和Bob在上完算法课后,决定自己编程实现一个贪吃蛇游戏,但粗心的Alice忘记编写在随机位置生成蛋的代码了,聪明的Bob想出了个好办法,将游戏玩法变为:给出初始蛇的位置与蛇头移动方向,再给出操作序列,求蛇最后所在的位置。Alice觉得这是个好主意,但为了更快的获得答案,她希望你能帮她写个程序,计算出蛇最后的位置。

游戏区域我们可以看成一个n行m列的矩阵,长度为k的蛇位置按照从头到尾的顺序标记为(x0,y0),(x1,y1),...,(xk,yk),xi代表所在行数,yi代表所在列数。游戏通过WASD分别控制方向上左下右,*代表未进行操作,蛇仍按原方向前进。无论是否改变方向,蛇都会以1的速度匀速前进。当蛇的移动超出边界,即判定蛇死亡。

Input


多组测试样例,第一行一个整数T,表示测试样例组数。

对于每组测试样例:

第一行三个整数n,m,r。n和m含义与题目中所述一致,r表示操作序列长度。

第二行一个整数k,表示蛇的长度,一个大写字母(WASD),表示蛇的初始移动方向。

第三四行表示蛇从头到尾的顺序初始所在的位置。

第三行k个整数,以空格分隔,代表xi。

第四行k个整数,以空格分隔,代表yi。

第五行一个长度为r的字符串,代表操作序列。

所有输入均保证合法。


数据规模:0<T<=40; 1000<=n,m<=1000000; 0<r<=1000; 0<k<=100000; 0<=xi<n; 0<=yi<m;


Output

如果在操作过程中蛇已经死亡,在一行中输出(不含引号):"GAME OVER!"

如果操作序列结束蛇仍存活,则按从头到尾的顺序输出两行,每行整数以空格分隔:

第一行k个整数代表蛇最终位置的xi,且行末不能有多余空格。

第二行k个整数代表蛇最终位置的yi,行末不能有多余空格

Sample Input

2
1000 1000 3
3 W
5 6 6
6 6 5
DSD
1000 1000 3
3 W
2 3 4
5 5 5
***

Sample Output

6 6 5
8 7 7
GAME OVER!

HINT

操作序列保证蛇的移动不会撞到自己,每次先进行方向的操作,再进行移动。

Source

[Submit][Status]