G - 跳跃序列

得分：$600$分

问题描述

考虑一个无限的二维坐标平面。 起初，高桥站在$(0,0)$点，他每次可以选择朝上、朝下、朝左或者朝右四个方向之一进行一次跳跃。 每次跳跃的长度是固定的，具体来说，第$i$次跳跃的长度为$D_i$。 判断是否存在一种方法使得高桥在做完$N$次跳跃后正好到达$(A,B)$点。如果存在，给出一种满足条件的方法。

这里，对于每个方向来说，从$(X, Y)$点向这个方向跳跃$D$距离，会到达下面的点：

• 向上：$(X,Y) \to (X,Y+D)$
• 向下：$(X,Y) \to (X,Y-D)$
• 向左：$(X,Y) \to (X-D,Y)$
• 向右：$(X,Y) \to (X+D,Y)$。

约束

• $1 \leq N \leq 2000$
• $\lvert A\rvert, \lvert B\rvert \leq 3.6\times 10^6$
• $1 \leq D_i \leq 1800$
• 输入中的所有值都为整数。

输入

输入从标准输入中提取，格式如下：

$N$ $A$ $B$

$D_1$ $D_2$ $\ldots$ $D_N$

输出

在第一行输出Yes，如果存在所需跳跃的序列；否则输出No。
如果存在所需跳跃的序列，第二行输出一种满足条件的跳跃序列，由长度为$N$的字符串$S$组成，字符串由如下字符组成：U、D、L、R，具体要求如下：

• 如果第$i$次跳跃朝上，则第$i$个字符应为U；
• 如果第$i$次跳跃朝下，则第$i$个字符应为D；
• 如果第$i$次跳跃朝左，则第$i$个字符应为L；
• 如果第$i$次跳跃朝右，则第$i$个字符应为R。

3 2 -2
1 2 3

Yes
LDR

如果高桥按照“左、下、右”的顺序进行跳跃，他会从$(0,0)$点依次移动到$(-1,0)$，然后移动到$(-1,-2)$，最后移动到$(2,-2)$点，正好到达目的地$(2,-2)$。

2 1 0
1 6

No

无法在两次跳跃后正好到达$(1, 0)$。

5 6 7
1 3 5 7 9

Yes
LRLUR