问题描述

在现代化的仓库中，机器人被用来取货。为确保机器人在抵达目的地时不会相互碰撞，需要进行周密的规划。当然，所有仓库都是矩形的，且每个机器人占据直径为1米的圆形地面空间。假设有N个机器人，编号从1到N。你将了解每个机器人的位置和朝向，以及所有指令——机器人会严格（且机械地）遵循这些指令。指令按顺序执行，没有两个机器人同时移动：一个机器人完成移动后，下一个才会开始移动。

如果机器人试图移动到仓库区域外，则会撞墙；如果两个机器人试图占据同一位置，则会相互碰撞。

输入格式

输入的第一行是K，即测试用例的数量。每个测试用例以一行开始，包含两个整数1 ≤ A, B ≤ 100，表示仓库的尺寸（单位：米）。A是东西方向的长度，B是南北方向的长度。

第二行包含两个整数1 ≤ N, M ≤ 100，分别表示机器人数量和指令数量。

接下来N行，每行包含两个整数1 ≤ Xi ≤ A, 1 ≤ Yi ≤ B和一个字母（N、S、E或W），按1到N的顺序给出每个机器人的起始位置和朝向。没有两个机器人从同一位置出发。

指令格式

最后有M行，按顺序给出指令，格式如下：
<机器人编号> <动作> <重复次数>

其中动作可以是：

• L：左转90度
• R：右转90度
• F：前进1米

重复次数满足1 ≤ <重复次数> ≤ 100。

输出格式

每个测试用例输出一行：

• 若机器人i撞墙，输出"Robot i crashes into the wall"（当Xi=0、Xi=A+1、Yi=0或Yi=B+1时视为撞墙）。
• 若机器人i与机器人j碰撞（i为移动的机器人），输出"Robot i crashes into robot j"。
• 若无碰撞，输出"OK"。

仅报告第一次发生的碰撞。

输入样例1

4  
5 4  
2 2  
1 1 E  
5 4 W  
1 F 7  
2 F 7  
5 4  
2 4  
1 1 E  
5 4 W  
1 F 3  
2 F 1  
1 L 1  
1 F 3  
5 4  
2 2  
1 1 E  
5 4 W  
1 L 96  
1 F 2  
5 4  
2 3  
1 1 E  
5 4 W  
1 F 4  
1 L 1  
1 F 20  

输出样例1

Robot 1 crashes into the wall  
Robot 1 crashes into robot 2  
OK  
Robot 1 crashes into robot 2  

题目来源

Nordic 2005