만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Insane Drift

시간 제한0.5초메모리 제한1024 MB

요약
원점에서 출발한 차량이 같은 명령을 연속할 때마다 이동 거리가 두 배로 늘어날 때, 4000번 이하의 명령으로 (X, Y)에 도달할 수 있는지 판단하고 가능하면 명령 순서를 출력합니다.
난이도

보통10점 중 7점

유형
수학, 그리디, 비트 연산
정답자
아직 제출이 없습니다

문제

무한히 넓은 2차원 좌표평면의 원점에 채완이가 자동차를 타고 있다. 채완이는 아래 두 가지 조작 중 하나를 선택해서 자동차를 움직일 수 있다.

  • R: 자동차를 xx 좌표가 증가하는 방향으로 움직인다. R을 kk번 연속으로 선택했다면 2k−12^{k-1}만큼 이동한다.
  • U: 자동차를 yy 좌표가 증가하는 방향으로 움직인다. U를 kk번 연속으로 선택했다면 2k−12^{k-1}만큼 이동한다.

채완이는 위 조작을 최대 4000번 시행해서 (X,Y)(X, Y) 위치에 도달하려고 한다. 채완이가 그 좌표에 도달할 수 있는지 판별하고, 도달할 수 있다면 조작 방법을 아무거나 하나 구하라. 모든 조작을 시행한 뒤 자동차가 정확히 (X,Y)(X, Y)에 있어야만 도달한 것으로 본다.

입력

첫째 줄에 XX와 YY가 공백으로 구분되어 주어진다. (0≤X,Y≤10180 \le X, Y \le 10^{18}, (X,Y)≠(0,0)(X, Y) \neq (0, 0))

출력

(X,Y)(X, Y)에 도달할 수 있다면 R과 U 문자로만 이루어진 길이 1 이상 4000 이하의 문자열을 출력한다. 문자열의 문자 순서대로 자동차를 움직였을 때 자동차가 정확히 (X,Y)(X, Y)에 놓여야 한다. 가능한 답이 여러 가지라면 그중 아무거나 출력해도 된다.

도달할 수 없다면 impossible을 출력한다.

예제2

  1. 예제 1

    입력
    8 3
    
    예상 출력
    RURRURRUR
    
  2. 예제 2

    입력
    0 16
    
    예상 출력
    impossible