救命!一个机器人逃出了我们的实验室,我们需要帮助找到它。
实验室位于坐标平面的 (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 个时刻的位置:我们知道在 ti 时刻机器人位于点 (xi, yi)。有了这些数据,要么有助于确定什么程序可以加载到机器人中,要么确定没有可能的程序符合数据并且机器人一定已经损坏。
输入
输入的第一行包含两个空格分隔的整数 n 和 l (1 ≤ n ≤ 2·105, 1 ≤ l ≤ 2·106)。
接下来的 n 行包含三个空格分隔的整数 — ti, xi, yi (1 ≤ ti ≤ 1018, - 1018 ≤ xi, yi ≤ 1018)。雷达数据按时间顺序给出,即,对于从 1 到 n - 1 的所有 i,ti < ti + 1。
输出
打印符合数据的任何可能的程序。如果没有程序满足数据,则打印一个单词“NO”(不带引号)。
示例
输入 #1
3 3 1 1 0 2 1 -1 3 0 -1
输出 #1
RDL
输入 #2
2 2 1 1 0 999 1 0
输出 #2
RL
输入 #3
2 5 10 10 0 20 0 0
输出 #3
NO