CF538G Berserk Robot

救命！一个机器人从我们的实验室逃跑了，我们需要帮助来找到它。 实验室位于坐标平面上的点 $(0,0)$，在时间 $0$ 时机器人就在这里。机器人的移动由一段程序控制——这是一个长度为 $l$ 的字符串，只包含字符 U、L、D、R。每一秒，机器人会执行程序中的下一个命令：如果当前坐标为 $(x,y)$，那么命令 U、L、D、R 会将它分别移动到 $(x,y+1)$、$(x-1,y)$、$(x,y-1)$、$(x+1,y)$。程序从时间 $0$ 开始执行，并且是循环的，即每执行 $l$ 秒后，程序会重新从第一个字符开始执行。不幸的是，我们不知道机器人离开实验室时加载的是哪一段程序。 我们的雷达在 $n$ 个时间点上侦测到了机器人的位置：我们知道在第 $i$ 个时间点 $t_i$，机器人位于点 $(x_i,y_i)$。根据这些数据，请你判断有没有可能的程序符合这些数据，如果有，请给出其中任意一个答案；如果没有，请判断机器人一定是故障了。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $l$（$1 \leq n \leq 2\times10^{5}$，$1 \leq l \leq 2\times10^{6}$）。 接下来的 $n$ 行，每行包含三个用空格分隔的整数——$t_i$、$x_i$、$y_i$（$1 \leq t_i \leq 10^{18}$，$-10^{18} \leq x_i, y_i \leq 10^{18}$）。雷达数据按时间顺序给出，即对所有 $i$ 满足 $1 \leq i \leq n-1$ 有 $t_i < t_{i+1}$。

输出任意一组可能的程序（即一个仅包含字符 U、L、D、R 的长度为 $l$ 的字符串），使其满足所有已知数据。如果不存在这样的程序，则输出一行 'NO'（不含引号）。

由 ChatGPT 5 翻译