AT_abc474_g.LRUD Moving 2

You are given positive integers $N$ and $K$.

There is an $N\times N$ grid. The cell at the $r$-th row from the top and the $c$-th column from the left is denoted as cell $(r,c)$.

Initially, a piece is placed on cell $(1,1)$.

You will perform the following operation exactly $N^2-1$ times so that the piece ends up in cell $(N,N)$:

• Move the piece one cell to a cell vertically or horizontally adjacent to the cell it is currently on.

Here, over the course of the movement, each of the $N^2$ cells must be visited exactly once. Cell $(1,1)$, where the piece is initially placed, is considered visited.

Determine whether there exists a sequence of operations where the piece moves one cell to the right exactly $K$ times, and if it exists, find one such sequence.

You are given $T$ test cases; solve each of them.

给你两个正整数 $N$ 和 $K$。

有一个 $N \times N$ 的网格。从上往下第 $r$ 行、从左往右第 $c$ 列的格子记为格子 $(r,c)$。

初始时，一枚棋子被放置在格子 $(1,1)$ 上。

你需要恰好执行 $N^2-1$ 次如下操作，使得棋子最终位于格子 $(N,N)$：

• 将棋子向当前所在格子的上、下、左、右四个相邻格子之一移动一格（即仅允许垂直或水平方向的单位移动）。

在整个移动过程中，$N^2$ 个格子中的每一个都必须恰好被访问一次。初始位置 $(1,1)$ 也被视为已访问。

请判断：是否存在一种操作序列，使得棋子恰好向右移动 $K$ 次？若存在，请构造出这样一种序列。

你将收到 $T$ 组测试数据，请对每组数据分别求解。

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

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$N$ $K$

输入从标准输入中以如下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例以如下格式给出：

$N$ $K$

Output the answers for the test cases in order, separated by newlines.

For each test case, if there is no sequence of operations satisfying the condition, output No.

If there exists a sequence of operations satisfying the condition, output it in the following format:

Yes
$S_1S_2\dots S_{N^2-1}$

Here, $S_k$ represents the $k$-th move, and is one of the following:

• $S_k=$ L if the piece moves one cell to the left
• $S_k=$ R if the piece moves one cell to the right
• $S_k=$ U if the piece moves one cell up
• $S_k=$ D if the piece moves one cell down

If there are multiple sequences of operations satisfying the condition, any of them will be accepted.

按测试用例的顺序输出答案，各答案之间用换行符分隔。

对于每个测试用例，若不存在满足条件的操作序列，则输出 No。

若存在满足条件的操作序列，则按如下格式输出：

Yes
$S_1S_2\dots S_{N^2-1}$

其中，$S_k$ 表示第 $k$ 步操作，取值为以下之一：

• $S_k=$ L：表示棋子向左移动一格；
• $S_k=$ R：表示棋子向右移动一格；
• $S_k=$ U：表示棋子向上移动一格；
• $S_k=$ D：表示棋子向下移动一格。

若存在多个满足条件的操作序列，输出任意一个即可。

Sample 1 Explanation:
Consider the first test case.

By moving from cell $(1,1)$ in order to cells $(1,2),(1,3),(2,3),(2,2),(2,1),(3,1),(3,2),(3,3)$, you can move one cell to the right four times and reach cell $(3,3)$.

Constraints

• $1\le T\le 5\times 10^3$
• $2\le N\le 10^3$
• $0\le K\le N^2-1$
• The sum of $N^2$ over all test cases is at most $10^6$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。

通过从单元格 $(1,1)$ 出发，依次经过单元格 $(1,2)$、$(1,3)$、$(2,3)$、$(2,2)$、$(2,1)$、$(3,1)$、$(3,2)$、$(3,3)$，你可以向右移动四次，最终到达单元格 $(3,3)$。

约束条件

• $1\le T\le 5\times 10^3$
• $2\le N\le 10^3$
• $0\le K\le N^2-1$
• 所有测试用例的 $N^2$ 之和不超过 $10^6$。
• 所有输入值均为整数。