32756번 - 분수 경로 스페셜 저지

문제

무한한 2ドル$차원 좌표 평면에서 $(0, 0)$에는 무한 정밀도의 실수를 저장할 수 있는 변수 $A$와 $B$가 있다. 처음에 $A$의 값은 0ドル$이고 $B$의 값은 1ドル$이다. 두 변수는 이동할 때 같이 이동하며 항상 서로 같은 좌표에 존재한다.

변수 $A,ドル $B$는 $(x, y)$에서 인접한 좌표 $(x+1, y),ドル $(x-1, y),ドル $(x, y+1),ドル $(x, y-1)$로 이동할 수 있다. 이때 이동한 거리는 1ドル$이라고 정의한다. 변수 $A,ドル $B$는 이동한 방향에 따라 값이 달라지는데 아래와 같이 달라진다.

• $(x, y)$에서 $(x+1, y)$로 이동 : 변수 $A$에 변수 $B$를 더한다. 즉, $A$ += $B$이며 문자 R로 표현한다.
• $(x, y)$에서 $(x-1, y)$로 이동 : 변수 $A$에서 변수 $B$를 뺀다. 즉, $A$ -= $B$이며 문자 L로 표현한다.
• $(x, y)$에서 $(x, y+1)$로 이동 : 변수 $B$에 2ドル$를 곱한다. 즉, $B$ *= 2ドル$이며 문자 U로 표현한다.
• $(x, y)$에서 $(x, y-1)$로 이동 : 변수 $B$를 2ドル$로 나눈다. 즉, $B$ /= 2ドル$이며 문자 D로 표현한다.

변수 $A$의 값이 정확히 $Z$가 되기 위한 경로를 구하여라.

입력

첫 번째 줄에 정수 $n,ドル $d$가 공백으로 구분되어 주어진다. 이는 $\displaystyle Z = \frac{n}{d}$임을 의미한다.

출력

만약 변수 $A$의 값이 $Z$가 될 수 있다면

• 첫 번째 줄에 변수 $A$의 값이 $Z$가 되기 위한 이동 경로의 길이 $L$을 출력한다. 단, 경로의 길이는 0ドル$ 이상 1000ドル$ 이하여야 한다.
• 두 번째 줄에 길이가 $L$인 경로 문자열을 출력한다. 그중 $i$번째 문자는 $i$번째 이동 종류를 의미한다. 출력하는 문자는 R, L, U, D 중 하나여야 한다. 가능한 경로가 여러 가지라면 그중 아무거나 하나를 출력한다.

만약 변수 $A$의 값이 $Z$가 될 수 없다면 -1을 대신 출력한다.

제한

• 0ドル \le |n| \le 10^{18}$
• 1ドル \le d \le 10^{18}$

힌트