상자 밀기

어떤 기계가 직사각형 방의 바닥에 놓인 단위 상자들을 밀어 정리한다. 모든 상자는 바닥에 놓인 한 변의 길이가 $1$인 정사각형이며, 방의 네 벽은 각각 안쪽으로 정수 단위만큼 이동하라는 명령을 받을 수 있다. 벽이 이동하면 그 경로에 있는 상자들을 함께 민다. 이 기계는 신중해서, 어떤 벽이 그 이상 나아가면 반대쪽 벽에 이미 빈틈없이 밀착된 상자들을 으스러뜨리게 되는 상황이면 도중에 멈추어 안전하게 갈 수 있는 만큼만 이동한다. 각 밀기가 끝나면 벽은 원래 자리로 되돌아온다.

상자의 위치는 그 왼쪽 위 모서리의 좌표 $(r, c)$로 나타낸다. 여기서 $r$은 위쪽 벽으로부터의 거리, $c$는 왼쪽 벽으로부터의 거리이다.

예를 들어 높이가 12, 너비가 16인 방에 상자들의 왼쪽 위 모서리가 (1,13), (3,2), (6,2), (6,4), (6,6), (7,6), (8,9)에 있다고 하자.

위쪽 벽에 아래로 3만큼 이동하라고 명령하면 문제없이 수행되어, (1,13)에 있던 상자가 (3,13)으로 밀려난다. 이어서 오른쪽 벽에 왼쪽으로 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 형식이다. 여기서 direction은 down, left, up, right, done 중 하나이고 m은 양의 정수이다.

• down m: 위쪽 벽을 아래로 $m$만큼 이동시킨다.
• up m: 아래쪽 벽을 위로 $m$만큼 이동시킨다.
• left m: 오른쪽 벽을 왼쪽으로 $m$만큼 이동시킨다.
• right m: 왼쪽 벽을 오른쪽으로 $m$만큼 이동시킨다.
• done: 이 데이터 집합의 끝을 나타내며 뒤에 숫자가 오지 않는다.

모든 데이터 집합의 끝은 0 0만 있는 줄로 표시된다.

각 데이터 집합마다 정확히 한 줄을 출력한다.

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

여기서 $d$는 1부터 시작하는 데이터 집합 번호이고, 각 쌍 $(r_i, c_i)$는 상자들의 최종 위치를 위에서 아래로, 같은 높이에서는 왼쪽에서 오른쪽 순서로 나열한 것이며, 하나의 공백으로 구분한다.