AT_dwango2017final_d 「ドワンゴからの挑戦状」製作秘話

尼科尼科电视酱正在为 dwango 主办的编程竞赛「来自 Dwango 的挑战书」准备题目。题目如下： - 给定一个长度为 $N$ 的数列 $a_1, a_2, \ldots, a_N$，需要处理 $Q$ 个查询。 - 对于第 $i$ 个查询，提供了 $l_i, r_i, x_i$，执行以下操作： - 将 $x_i$ 加到数列中第 $l_i$ 到第 $r_i$ 项的每一个元素。然后，输出这些元素的最大值。 比赛前一天，电视酱顺利完成了准备工作并安心入睡。然而，第二天早上醒来时，她发现电脑完全无法启动。 尽管如此，电视酱成功恢复了数据，但数列的初始值 $a_1, a_2, \ldots, a_N$ 却没有恢复。 于是，她创造了一个新的问题：恢复这个初始数列。 现在，题目变化为： 你将获得 $N$ 和 $Q$，每个查询的参数 $l_i, r_i, x_i$ 以及结果 $y_i$。 你需要判断是否存在这样的原始数列 $a_1, a_2, \ldots, a_N$，如果存在，请输出一个可能的数列。 请注意，电视酱记得数列 $a_1, a_2, \ldots, a_N$ 中的所有元素都是整数，且绝对值不超过 $10^{18}$。因此，输出的数列也需满足这一条件。 题目保证，无论数列值有无这样的约束，都不会影响测试用例中是否存在满足条件的数列。

输入以以下格式给出： > $N$ $Q$ $l_1$ $r_1$ $x_1$ $y_1$ $l_2$ $r_2$ $x_2$ $y_2$ $\ldots$ $l_Q$ $r_Q$ $x_Q$ $y_Q$

如果不存在满足条件的数列 `a_i`，则输出 `NG`。 如果存在，请输出 `OK`，并在下一行按照顺序输出 $a_1, a_2, \ldots, a_N$，各元素之间用空格分隔。

- 所有输入均为整数 - $1 \leq N \leq 200,000$ - $1 \leq Q \leq 200,000$ - $1 \leq l_i \leq r_i \leq N$ - $|x_i| \leq 10^9$ - $|y_i| \leq 10^9$ ### 样例解释 1 对于实例中，加 $100$ 后 $a_1, a_2, a_3$ 的最大值为 $300$，例如 $200, 200, 200$ 就是一个满足条件的数列。 ### 样例解释 2 在这个例子中，第一个查询要求 $a_1, a_2, a_3$ 的最大值为 $100$，而第二个查询为 $101$。这明显存在矛盾，因此输出 `NG`。 ### 样例解释 3 对于这里的输入，只要第二个值满足约束，其他值如何都无所谓。 **本翻译由 AI 自动生成**