N * N 크기의 평지에서 통나무를 원하는 위치로 옮기고자 한다.

통나무는 항상 수평 또는 수직 모양으로 폭이 1, 길이가 I 인 모양이다. 통나무를 옮기고자 하는데 곳곳에 장애물이 있다.

따라서 통나무를 적절하게 계획하여 움직여야 한다. 움직임을 U,D,L,R 이라고 하고 각각 위,아래,왼쪽,오른쪽으로 한칸 움직이는 것을 뜻한다. 통나무를 움직이는 또 다른 방법으로 회전 T 가 있다. 회전을 하기 위해서는 통나무의 주변에 장애물이 없어야 한다.

왼쪽 그림의 상태에서는 빗금친 부분에 장애물이 없어야 오른쪽 그림과 같이 회전이 가능하다.

필요한 움직임 (U,D,L,R,T)를 최소로 하여 통나무를 원하는 위치로 옮기는 프로그램을 작성하시오.

입력 형식

입력의

• B 는 원래 통나무의 위치,
• E 는 옮기고자 하는 위치,
• 0 은 장애물 없음,
• 1 은 장애물 있음을 의미한다.

출력 형식

• 첫 줄은 최소 동작의 횟수,
• 둘째 줄 부터 통나무의 움직임을 차례로 출력한다.

입출력 의 예

입력

5
B0011
B0000
B0000
11000
EEE00

출력

9
R
T
R
R
D
D
D
L
L

출처: koi 고등 기출