408965: GYM103389 I 驾驶卡丁车

小Q正在设计一款2D卡丁车游戏，你的任务是帮助小Q实现其中的一部分功能。

在这款游戏中，游戏地图是一张 $$$n$$$ 行 $$$m$$$ 列的网格，从上到下依次编号为第 $$$1$$$ 行到第 $$$n$$$ 行，从左往右依次编号为第 $$$1$$$ 列到第 $$$m$$$ 列，其中第 $$$i$$$ 行第 $$$j$$$ 列的格子的坐标为 $$$(i,j)$$$，每个格子要么是可以通行的平地，要么是不可通行的障碍。

在地图上的某个平地格子处有一辆由玩家操控的卡丁车。卡丁车的移动速率为 $$$v$$$，并且一共有8种可能的朝向，分别为：

• "上"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x-1,y)$$$。
• "下"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x+1,y)$$$。
• "左"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x,y-1)$$$。
• "右"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x,y+1)$$$。
• "左上"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x-1,y-1)$$$。
• "右上"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x-1,y+1)$$$。
• "左下"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x+1,y-1)$$$。
• "右下"：前进一步时，将从 $$$(x,y)$$$ 移动到 $$$(x+1,y+1)$$$。

一开始卡丁车朝上位于某个平地格子处，其初始移动速率为 $$$v=0$$$。接下来玩家将依次输入 $$$q$$$ 条操作指令，每条操作指令是下列中的一种：

• "L"：卡丁车朝向往左转 $$$45$$$ 度。
• "R"：卡丁车朝向往右转 $$$45$$$ 度。
• "U"：卡丁车的速率由 $$$v$$$ 增大至 $$$v+1$$$。
• "D"：卡丁车的速率由 $$$v$$$ 减小至 $$$\max(v-1,0)$$$。

在执行完每条操作指令后，卡丁车都会沿着其朝向前进 $$$v$$$ 步，在移动结束后才会继续响应后续指令。在前进的过程中，如果某一步尝试驶入某个障碍格子或者尝试驶出地图，那么说明卡丁车发生了碰撞，它将就此结束移动，在保持朝向的同时速率 $$$v$$$ 降低为 $$$0$$$。特别要注意的是，当朝向是斜$$$45$$$度时，为了防止"穿模"现象的发生，如果卡丁车两侧都是障碍，那么卡丁车同样将被认为发生了碰撞。例如卡丁车朝向右下，现在将从 $$$(x,y)$$$ 移动到 $$$(x+1,y+1)$$$，那么如果 $$$(x+1,y)$$$ 和 $$$(x,y+1)$$$ 都是障碍，则卡丁车发生了碰撞。

请写一个程序，在执行完每条操作指令后且卡丁车完成移动之后，汇报卡丁车的坐标以及这次移动过程中是否发生了碰撞。

第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$1\leq n,m\leq 50$$$)，表示地图的尺寸。

接下来 $$$n$$$ 行，第 $$$i$$$ 行包含一个长度为 $$$m$$$ 的字符串，其中第 $$$j$$$ 个字符描述格子 $$$(i,j)$$$。如果它是"."，则说明 $$$(i,j)$$$ 是平地；如果它是"#"，则说明 $$$(i,j)$$$ 是障碍；如果它是"*"，则说明 $$$(i,j)$$$ 是平地，且卡丁车位于此。输入数据保证存在恰好一个"*"。

接下来一行包含一个正整数 $$$q$$$ ($$$1\leq q\leq 500$$$)，表示指令的数量。

接下来一行包含一个长度为 $$$q$$$ 的字符串，每个字符是四种指令中的一种，依次描述每条指令。

输出 $$$q$$$ 行，第 $$$i$$$ 行输出执行完第 $$$i$$$ 条指令且卡丁车完成移动之后的相关信息。如果这一次卡丁车没有发生碰撞，那么输出"x y"；如果这一次卡丁车发生了碰撞，那么输出"Crash! x y"。其中 $$$x$$$ 和 $$$y$$$ 表示卡丁车的坐标为 $$$(x,y)$$$。

5 4
....
##..
..#.
.*..
....
12
URULLULLLLUD

3 2
Crash! 3 2
Crash! 3 2
3 2
3 2
Crash! 3 2
3 2
3 2
3 2
3 2
4 3
4 3

10 10
####....##
##.......#
#....##...
#...####..
#...####..
#...####..
#.........
#...####..
....####..
*...####..
16
UURUURRULUULLUUD

9 1
Crash! 9 1
9 1
8 2
6 4
Crash! 6 4
6 4
7 5
7 6
7 8
Crash! 7 10
7 10
7 10
6 10
4 10
3 10