该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

【背景】

伟大的贪吃蛇于今日回归了它忠实的迷宫，但历经多年的征战使得它的眼睛受到了伤害，可怜的蛇蛇现在只能让它忠诚的大臣告诉它前进的方向，你能帮它算一算大臣给的路线靠不靠谱吗（大臣该不该杀吗）

【描述】

这是一片有限大小的迷宫，蛇蛇会从它的巢穴出发，每单位时间移动一格，在刚开始的时候，蛇蛇只有一格长，如果蛇蛇吃到食物，它就会变长一格

蛇蛇在移动的时候可能会想要转头，但是愚蠢的蛇蛇不知道它如果转头180°就会迎来死亡

蛇蛇的眼睛也不太好使，它不知道哪里有障碍物或者食物，只能随机乱跑，如果它撞到了墙或者撞到了自己的身子，则这轮尝试结束

【流程】

定义迷宫坐标系如下图所示（红色虚线为迷宫最外侧位置，超出该范围为迷宫边界）

首先应该接收迷宫边界和蛇蛇的初始坐标进行数组初始化，利用一个迷宫大小的数组来存储所有数据，另外还需要额外存储蛇头的坐标与前进方向（初始时设置为向上）

然后接收第一条指令，读取时间码，然后进行迭代操作

首先判断蛇蛇前进方向，再判断前进方向上是否存在障碍物或者食物或者蛇蛇的身子，

• 如果存在障碍物或者蛇蛇则输出[当前时间码] d并退出程序
• 如果存在食物则将该格设置为蛇蛇的身子，输出[当前时间码] f，将蛇头坐标指向该位置，进入下一次循环
• 如果什么都不存在则将该格设置为蛇蛇的身子，并将蛇头坐标指向该位置，同时从蛇头开始向后遍历寻找蛇尾，清除蛇尾所在格

在以上步骤完成后视为完成一次迭代，将时间码+1，然后开始下一次迭代

[Tips] 可以定义数组中0为空气、1为障碍物、2为食物、3为向上的蛇蛇身子、4为向下的蛇蛇身子、以此类推，遍历时根据该值决定向哪个方向搜索，若该方向不存在蛇蛇身子则认为到达蛇尾

直至迭代至该时间码前一时刻，然后判断该指令类型

• 若该指令为放置障碍物或食物指令，则立即修改数组中对应的值，然后继续迭代
• 若该指令为转向指令，判断该方向是否与目前方向相差180°，若是，则输出[当前时间码] d并退出程序，否则修改前进方向，然后继续迭代

当所有指令都执行完毕后，退出程序

输入格式

{m} {n}
{x} {y}
{l}
{t x y c}
···

首先输入m n，表示迷宫边界，$m/n \in [0, 50]$

然后输入x y，表示蛇蛇的初始坐标，该坐标一定位于迷宫边界内，且不在蛇身上

接着输入l，表示接下来将输入l条指令

最后每行将表示一条指令

t表示当前指令执行的时间码，该时间码为正整数，且小于65535，保证时间码为递增数列

x y c含义见下表，所有输入的x y均在迷宫边界内

Tips: 对于40%的数据点，仅存在x维度，n始终为1

输出格式

{t c}
···

输出如示指令，t表示时间发生时间码，c表示事件类型

注意：每条指令后都需要换行（含最后一条指令）

10 1
6 0
2
0 0 0 r
10 0 0 b

3 d

10 1
2 0
4
0 0 0 r
3 6 0 f
4 8 0 f
10 0 0 b

3 f
5 f
7 d

提示

无