Area Inside a Cycle

You are given two integers $N$ and $K$. Let $S$ be the set of points in the plane whose $x$- and $y$-coordinates are both integers between $1$ and $N$, inclusive.

Start at $(1,1)$. Each move must go one unit up, down, left, or right to an adjacent grid point. The destination of every move must belong to $S$. Visit every point in $S$, and return to $(1,1)$ on the final move. Every point must be visited exactly once, except for the final return to the starting point.

Determine whether the polygon formed by the route can have an interior area of exactly $K$. If it can, construct one such route.

The input is given from Standard Input in the following format:

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

For each test case, if no route satisfies the conditions, print No on one line.

Otherwise, print Yes on the first line. On the second line, print a string of length $N^2$ describing the moves in order. The string must contain only the following four characters:

• U: increase the $y$-coordinate by $1$.
• D: decrease the $y$-coordinate by .

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