题目描述

垃圾场里的报废汽车被一个装置压碎，该装置从侧面、前后、顶部和底部将汽车推入。结果是一块致密的金属。在这个问题中，你将模拟一个以类似方式工作的设备，但不会压碎任何东西，只会在二维空间中推动盒子。这些盒子都是正方形的，边长为单位，位于房间的地板上。房间的每一面墙都可以编程为向内移动一定量，推动它可能碰到的任何盒子。与汽车破碎机不同，这种设备很敏感，如果它感觉到箱子靠墙堆放，如果再按下去可能会压碎它们，它就会停止。例如，假设我们有一个 $12$ 乘 $16$ 的房间，如下图所示。框的左上角（这就是我们在这个问题中如何定位它们）位于坐标 $(1,13)$（下面的框A）、$(3,2)$、$(6,2)$、$(6,4)$、$(6,6)$、$(7,6)$ 和 $(8,9)$（框G）处，其中第一个坐标表示与顶壁的距离，第二个坐标表示距左壁的距离。

假设顶墙向下移动 $3$ 个单位（然后撤退，因为墙总是会后退），然后右墙向左移动 $14$ 个单位。第一次移动可以毫无问题地进行，但第二次移动如果不压碎一些箱子就无法进行。因此，右墙将只移动 $13$ 单位，即它可以移动的最大距离，直到箱子紧紧地装在它和左墙之间。然后，这些框将处于下图所示的配置中。这些框的位置是 $(3,1)$、$(3,2)$、$(6,0)$、$(6,1)$、$(6,2)$、$(7,2)$、$(8,2)$。

输入格式

此问题将有多个数据集。每个数据集的第一行将是两个整数，给出房间的高度和宽度。（我们将把房间想象成一张纸，如上所示。）每个维度不超过 $20$。

下一行将包含一个整数 $n$ （$0 < n \le 10$），后面是 $n$ 对整数，每对整数都给出了一个盒子的位置，即与房间顶部和左侧墙壁的距离。

以下行将采用 direction m 的形式，其中方向可以是 down、left、up、right 或 done，$m$ 是一个正整数。例如，left 2 意味着试图将右墙向左移动 $2$ 个单位长度。done 表示您已经完成了这组框的推送。当然，在 done 后不会有整数 $m$。

测试数据以 0 0 结尾。

输出格式

对于每个数据集，您需要输出一行一个字符串：

Data set d ends with boxes at locations (r1, c1) (r2, c2) ... (rn, cn).

其中 $(r_i,c_i)$ 是从上到下、从左到右给出的框的位置（用一个空格隔开），$d$ 是数据集编号（从 $1$ 开始）。

翻译提供者：csyc5586

12 16
7 1 13 3 2 6 2 6 4 6 6 7 6 8 9 
down 3
left 14
done
4 4
3 1 0 2 1 2 3
right 3 
up 2 
left 1 
done 
0 0

Data set 1 ends with boxes at locations (3,1) (3,2) (6,0) (6,1) (6,2) (7,2) (8,2).
Data set 2 ends with boxes at locations (0,2) (1,1) (1,2).