프로그램 속의 프로그램 (Small)

동서로 무한히 뻗은 도로 위에 로봇이 한 대 서 있고, 로봇은 케이크를 하나 들고 있다. 도로에는 양쪽 방향으로 1마일마다 가로등이 하나씩 서 있다. 로봇은 출발한 가로등에서 동쪽으로 정확히 $N$번째 가로등에 케이크를 내려놓아야 한다. 가는 경로는 상관없고, 케이크를 내려놓는 가로등만 맞으면 된다.

로봇은 기억 장치가 아주 작고 스스로 판단하지 못한다. 그래서 출발하기 전에 프로그램을 하나 넣어 주어야 한다. 프로그램은 다음 형식의 명령문 한 개 이상으로 이루어진다.

<S> <M> -> <action>

이 명령문은 다음 두 조건을 모두 만족할 때 실행된다.

1. 로봇의 상태가 S이다.
2. 로봇이 서 있는 가로등에 적힌 수가 M이다.

<action>은 다음 둘 중 하나다.

1. <D> <NS> <NM>: 현재 가로등에 수 NM을 적고, 상태를 NS로 바꾸고, 방향 D로 가로등 한 칸만큼 이동한다. D는 서쪽이면 W, 동쪽이면 E이다.
2. R: 현재 위치에 케이크를 내려놓고 스스로 파괴된다.

S와 M이 모두 같은 명령문을 두 개 이상 출력하면 로봇은 오작동해서 케이크를 부순다. 로봇이 상태 X로 수 Y가 적힌 가로등에 서 있는데 S가 X이고 M이 Y인 명령문이 없으면, 로봇은 혼란에 빠져 케이크를 먹어 버린다.

모든 상태와 모든 표시는 절댓값이 1,000,000 이하인 정수다. 로봇은 상태 0에서 출발하고, 처음에 모든 가로등에는 0이 적혀 있다.

$N$이 주어지면 로봇이 출발 지점에서 동쪽으로 $N$번째 가로등에 케이크를 내려놓도록 하는 프로그램을 출력한다. 프로그램은 명령문을 30개 이하로 써야 하고, 로봇의 이동 횟수는 $X$번을 넘지 않아야 한다. 조건을 만족하는 프로그램은 여러 가지이므로, 출력에서 그중 하나를 정확히 지정한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개 줄에 정수 $N$이 한 줄에 하나씩 주어진다. $N$은 로봇이 케이크를 내려놓아야 하는 가로등의 번호다.

각 테스트 케이스마다 먼저 Case #x: 27을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 그다음 아래 명령문 27개를 이 순서 그대로 출력한다.

0 0 -> W 1 0
1 0 -> W 2 c0
2 0 -> W 3 c1
3 0 -> W 4 c2
4 0 -> W 5 c3
5 0 -> W 6 c4
6 0 -> W 7 c5
7 0 -> W 8 c6
8 0 -> W 9 c7
9 0 -> W 10 c8
10 0 -> E 11 4
11 0 -> W 12 0
11 1 -> E 11 1
11 2 -> E 11 2
12 0 -> W 12 0
12 1 -> W 12 2
12 2 -> E 13 1
12 3 -> W 12 3
12 4 -> E 14 4
13 0 -> E 12 3
13 1 -> E 13 1
13 2 -> E 13 2
13 3 -> E 13 3
14 0 -> R
14 1 -> E 14 1
14 2 -> E 14 2
14 3 -> E 14 3

c0부터 c8까지는 $N$에 따라 정해진다. $N$을 아홉 자리 이진수 $N = \sum_{j=0}^{8} b_j 2^j$, $b_j \in \{0, 1\}$로 쓰면 $c_j = 1 + b_j$이다. 즉 $N$의 $j$번째 이진 자릿수가 0이면 1을, 1이면 2를 적는다. 이 아홉 줄만 $N$에 따라 달라지고 나머지 열여덟 줄은 모든 $N$에서 같다.

• $1 \le T \le 15$
• $0 \le N \le 500$
• $X = 1000000$

출발 지점에서 서쪽으로 놓인 가로등 아홉 개가 $N$을 이진수로 저장한다. 가로등 하나가 한 자리를 맡고, 가장 낮은 자리가 출발 지점에 가장 가깝다. 표시 1은 자릿수 0을, 표시 2는 자릿수 1을 뜻한다. 상태 0부터 10까지가 이 아홉 자리를 적고 한 칸 더 서쪽에 경계 표시 4를 적으며, 상태 11은 출발 지점까지 동쪽으로 되돌아온다.

나머지는 반복 구간이다. 상태 12에서 로봇은 이미 지나온 가로등(표시 3)을 지나 서쪽으로 가서 저장된 수를 1 줄인다. 자릿수가 0인 가로등(표시 1)은 2로 바꾸고 계속 서쪽으로 가며, 처음 만난 자릿수가 1인 가로등(표시 2)을 1로 바꾸면 뺄셈이 끝난다. 뺄셈에 성공하면 상태 13이 동쪽으로 돌아가 아직 표시가 없는 첫 가로등에 3을 적고 한 칸 더 동쪽으로 간다. 이 이동이 동쪽으로 한 칸 나아가는 부분이다. 저장된 수가 이미 0이면 빌림이 경계 표시 4까지 닿고, 상태 14가 동쪽으로 가서 표시가 없는 첫 가로등에 케이크를 내려놓는다. 뺄셈은 정확히 $N$번 성공하므로 케이크는 출발 지점에서 동쪽으로 $N$번째 가로등에 놓인다. 이 프로그램은 명령문 27개를 쓰고 이동 횟수는 253029를 넘지 않는다.