描述

废品场里的报废汽车会在一种设备中被挤压，这种设备会从侧面、前后以及上下对汽车进行挤压，最终会得到一块紧凑的小金属块。在这个问题中，你要对一种类似的设备进行建模，但这种设备并不挤压任何东西，只是在二维平面上移动箱子。这些箱子都是边长为单位长度的正方形，并且被放置在一个房间的地面上。房间的每一面墙都可以被编程设置向内移动一定的距离，并且会推动它可能撞到的任何箱子。与汽车挤压设备不同的是，这个设备很灵敏，如果它检测到箱子已经堆叠在墙上，并且如果再继续挤压可能会压坏箱子时，它就会停止。

例如，假设我们在一个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 <= 10），后面跟着n对整数，每一对整数给出一个箱子的位置，即该箱子距离房间顶部墙壁和左侧墙壁的距离。接下来的行将是“方向 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).”

其中，(ri, ci)是箱子的位置，按照从上到下、从左到右的顺序给出（每个位置之间用一个空格隔开），d是数据集的编号（从1开始）。

输入数据 1

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

输出数据 1

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).

来源

2003年美国中东部地区竞赛