두 정수 , 가 주어진다. 평면 위에서 좌표와 좌표가 모두 이상 이하의 정수인 격자점들의 집합을 라 하자.
에서 출발하여 상하좌우로 인접한 격자점으로 한 칸씩 이동하려고 한다. 모든 이동의 도착점은 에 속해야 한다. 의 모든 점을 방문한 뒤, 마지막 이동으로 로 돌아와야 한다. 시작점으로 돌아오는 마지막 방문을 제외하면, 각 격자점을 정확히 한 번씩 방문해야 한다.
이 경로가 만드는 다각형의 내부 넓이가 정확히 가 되도록 할 수 있는지 판별하고, 가능하다면 그러한 경로를 하나 구성하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하는 경로가 없다면 한 줄에 No를 출력한다.
경로가 있다면 첫째 줄에 Yes를 출력하고, 둘째 줄에 이동 순서를 나타내는 길이 의 문자열을 출력한다. 문자열은 다음 네 문자로만 이루어져야 한다.
U: 좌표를 증가시킨다.D: 좌표를 감소시킨다.두 번째 테스트 케이스에서 출력한 경로는 , , , 을 차례로 방문한 뒤 로 돌아온다. 이 경로가 만드는 정사각형의 넓이는 이다.
는 테스트 케이스의 수이다. 각 케이스는 다음과 같은 형식으로 주어진다.
R: 좌표를 증가시킨다.L: 좌표를 감소시킨다.에서 출발하여 문자열의 문자들을 순서대로 수행했을 때, 문제에서 요구하는 모든 조건을 만족해야 한다. 출력의 대소문자는 구분한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.