사이클 내부의 넓이

두 정수 $N$, $K$가 주어진다. 평면 위에서 $x$좌표와 $y$좌표가 모두 $1$ 이상 $N$ 이하의 정수인 격자점들의 집합을 $S$라 하자.

$(1,1)$에서 출발하여 상하좌우로 인접한 격자점으로 한 칸씩 이동하려고 한다. 모든 이동의 도착점은 $S$에 속해야 한다. $S$의 모든 점을 방문한 뒤, 마지막 이동으로 $(1,1)$로 돌아와야 한다. 시작점으로 돌아오는 마지막 방문을 제외하면, 각 격자점을 정확히 한 번씩 방문해야 한다.

이 경로가 만드는 다각형의 내부 넓이가 정확히 $K$가 되도록 할 수 있는지 판별하고, 가능하다면 그러한 경로를 하나 구성하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 조건을 만족하는 경로가 없다면 한 줄에 No를 출력한다.

경로가 있다면 첫째 줄에 Yes를 출력하고, 둘째 줄에 이동 순서를 나타내는 길이 $N^2$의 문자열을 출력한다. 문자열은 다음 네 문자로만 이루어져야 한다.

• U: $y$좌표를 $1$ 증가시킨다.
• D: $y$좌표를 $1$ 감소시킨다.

• $1 \leq T \leq 10^6$.
• $1 \leq N \leq 2\,000$.