식당에서 일하기

어젯밤 톰은 정말 멋진 여자와 데이트를 했다. 그런데 신용카드를 깜빡하고 안 가져왔고 지갑에 현금도 없어서, 결국 식당에서 일하며 밥값을 갚게 되었다. 그의 일은 종업원이 테이블에서 접시를 가져오면 그것을 받고, 설거지 담당이 요청하면 접시를 넘겨주는 것이다. 접시는 테이블에서 가져온 순서와 똑같은 순서로 설거지되어야 한다. 그렇지 않으면 접시가 설거지되기까지 너무 오래 걸려 음식 찌꺼기가 눌어붙을 수 있기 때문이다. 접시를 모두 손에 들고 있는 것은 좋은 생각이 아니므로, 톰은 종업원이 접시를 건네주면 곧바로 테이블에 내려놓고, 설거지 담당에게 넘길 때가 되면 다시 집어 든다. 테이블에는 접시 더미를 두 개만 놓을 수 있으며, 이를 각각 더미 1, 더미 2라고 부른다. 톰이 쓸 수 있는 테이블은 이 하나뿐이다.

톰은 작년 SWERC에서 우승했으므로 분명히 효율을 잘 따질 수 있다. 그가 받는 접시와 요청의 순서가 주어질 때, 톰이 테이블 위에서 접시를 정리하는 아래에 설명된 구체적인 방식의 기록(transcript)을 출력해야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 수 $N$이 있는 줄로 시작하고 ($1 \le N \le 1000$), 이어서 $N$개의 줄이 오는데, 각 줄은 DROP m 또는 TAKE m 형태이며 $m > 0$은 내려놓거나 집어 드는 접시의 수이다. DROP m은 다음 사건이 종업원이 톰에게 접시 $m$개를 가져오는 것이어서 그가 테이블에 접시를 내려놓아야 함을 뜻하고, TAKE m은 다음 사건이 톰이 테이블에서 접시 $m$개를 집어 올바른 순서로 넘겨주는 것임을 뜻한다. 테이블에 접시가 $m$개보다 적을 때 TAKE m 명령을 받는 일은 없으며, DROP 연산에 해당하는 모든 $m$ 값의 합 $M$은 $100,000$을 넘지 않는다고 가정해도 된다. 마지막 요청 이후에도 톰의 테이블에 접시가 남아 있을 수 있는데, 톰이 식당이 닫을 때까지 있어야 하는 의무에서 벗어날 수도 있기 때문이다.

입력은 $N = 0$인 줄로 끝나며, 이 줄은 처리하지 않는다.

각 테스트 케이스에 대해, 톰이 수행하는 연산의 기록을 출력한다. 각 줄은 다음 중 하나이다.

• DROP 1 m 또는 DROP 2 m ($m > 0$): 종업원에게서 접시를 받아 더미 1(각각 더미 2)의 맨 위에 내려놓는 일을 총 $m$번 반복한다.
• TAKE 1 m 또는 TAKE 2 m ($m > 0$): 더미 1(각각 더미 2)의 맨 위에서 접시를 집어 설거지 담당에게 넘기는 일을 총 $m$번 반복한다.
• MOVE 1->2 m 또는 MOVE 2->1 m ($m > 0$): 더미 1(각각 더미 2)의 맨 위에서 접시를 집어 다른 더미의 맨 위에 내려놓는 일을 총 $m$번 반복한다.

톰은 항상 들어오는 접시를 더미 2에 내려놓고 항상 더미 1에서 설거지 담당에게 넘기며, 정확히 다음의 결정적(deterministic) 전략을 따른다(그 기록을 그대로 출력해야 한다).

• 각 DROP m 명령에 대해 DROP 2 m 한 줄을 출력한다.
• 각 TAKE m 명령을 순서대로 처리한다.
  • 더미 1에 현재 접시가 $a > 0$개 있으면, $k = \min(m, a)$로 TAKE 1 k를 출력하고, 아직 필요한 접시 수를 $k$만큼 줄인다.
  • 그 뒤에도 접시가 더 필요하면(더미 1이 이제 비었다면), 더미 2의 현재 접시 수 $b$로 MOVE 2->1 b를 출력하고 — 이는 더미 2의 모든 접시를 더미 1로 옮긴다 — 이어서 아직 필요한 접시 수 $r$로 TAKE 1 r을 출력한다.

명령은 주어진 순서 그대로 처리한다. 이 전략은 모든 접시를 도착한 순서와 똑같이 설거지하며, 출력 줄은 최대 $3N$개, 접시 이동 횟수는 최대 $3M$번이다. 서로 다른 케이스의 출력 사이에는 빈 줄을 하나 둔다.