Pushing Boxes

A machine pushes unit boxes around the floor of a rectangular room. Every box is a $1 \times 1$ square resting on the floor, and each of the room's four walls can be told to move inward by a whole number of units, shoving along any boxes it runs into. The machine is careful: if a wall would crush boxes that are already packed tightly against the opposite wall, it stops early and moves only as far as it safely can. After each push the wall retreats to its original position.

A box's location is given by the coordinates $(r, c)$ of its upper-left corner, where $r$ is the distance from the top wall and $c$ is the distance from the left wall.

For example, consider a room 12 units tall and 16 units wide whose boxes have upper-left corners at (1,13), (3,2), (6,2), (6,4), (6,6), (7,6), and (8,9).

Telling the top wall to move down 3 units succeeds, and the box at (1,13) is pushed down to (3,13). Next, telling the right wall to move left 14 units cannot be done without crushing boxes, so it moves only 13 units — the farthest it can go until the boxes are packed tightly between it and the left wall. The boxes then rest at (3,1), (3,2), (6,0), (6,1), (6,2), (7,2), and (8,2).

A push acts along a single axis. A vertical push (from the top or bottom wall) moves boxes only up or down within their own columns; a horizontal push (from the left or right wall) moves boxes only left or right within their own rows. A wall pushes a box only when it — or a chain of boxes ahead of it — actually reaches that box, so boxes with empty space in front of them are left untouched.

The input contains several data sets. The first line of each data set holds two integers: the height and the width of the room (each at most 20). The next line holds an integer $n$ ($0 < n \le 10$) followed by $n$ pairs of integers; each pair gives a box's location as its distances from the top and left walls.

Each remaining line of the data set has the form direction m, where direction is one of down, left, up, right, or done, and m is a positive integer.

• down m moves the top wall down $m$ units.
• up m moves the bottom wall up $m$ units.
• left m moves the right wall left $m$ units.
• right m moves the left wall right $m$ units.
• done marks the end of this data set and is not followed by a number.

The list of data sets ends with a line containing 0 0.

For each data set, print exactly one line:

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

Here $d$ is the data set number, counting from 1, and each pair $(r_i, c_i)$ is a final box location, listed top-to-bottom and then left-to-right within a row, separated by single spaces.