← 返回题目列表

AtCoder · dwango2017final_d

D. 《Dwango的挑战》制作背后的秘密故事

中文机器翻译题面 查看原题

配点 : 1300 点

問題文

Niconico TV-chan 是由 dwango 赞助的编程竞赛。 我正在准备“Dwango的挑战”这一题。问题如下。 给出

  • 长度 N 序列 有 a_1,\ a_2,\ ...,\ a_N ,其中 处理 Q 查询
  • i 查询中 给定 l_i,\ r_i,\ x_i ,执行以下操作:
  • a_{l_i},\ a_{l_i+1},\ ...,\ a_{r_i} 分别 添加 x_i 。在那之后, 输出a_{l_i},\ a_{l_i+1},\ ...,\ a_{r_i} 的最大值。

比赛前一天,niconico TV酱完成了准备就上床睡觉了。 那天早上我醒来时,我的电脑完全坏了。

Niconico TV努力恢复数据,但是 序列的初始值 只有 a_1,\ a_2,\ ...,\ a_N 无法恢复。

然而,Nico Nico TV-chan利用了这一逆境,成功地制造了一个新问题。 就是这个数列 问题是恢复 a_1,\ a_2,\ ...,\ a_N 。

现在问题来了。

N 和 Q 及查询内容 l_i,\ r_i,\ x_i及其输出 y_i 。

你有原始序列 a_1,\ a_2,\ ...,\ a_N 判断是否存在可能的事情,如果有则标记为 1 请输出一个。

然而,Nico Nico TV-chan a_1,\ a_2,\ ...,\ a_N 均为整数,其绝对值为 10^{18} 我记得它在下面。 因此,请确保输出满足此约束。

对于这次给出的所有测试用例,这 无论是否对 a_1,\ a_2,\ ...,\ a_N 的值进行限制, 保证了可能的原始序列的存在不会改变。

制約

  • 所有输入均为整数
  • 1 ≦ N ≦ 200,000
  • 1 ≦ Q ≦ 200,000
  • 1 ≦ l_i ≦ r_i ≦ N
  • |x_i| ≦ 10^9
  • |y_i| ≦ 10^9

入力

输入将以以下格式从标准输入给出。

N Q
l_1 r_1 x_1 y_1
l_2 r_2 x_2 y_2
:
l_q r_q x_q y_q

出力

如果序列满足条件 如果 a_i 不存在 NG 。

如果存在 OK 和下一行 请按顺序输出 a_1, a_2, ..., a_N ,以空格分隔。 添加


入力例 1

3 1
1 3 100 300

出力例 1

OK
200 200 200 

100 后 a_1, a_2, a_3 的最大值为 300 所以,例如, 200, 200, 200 满足条件。


入力例 2

3 2
1 3 0 100
1 3 0 101

出力例 2

NG

在这种情况下, 当 1 在第二个查询中 a_1, a_2, a_3 的最大值 输出 100 和 输出 2 在第二个查询中 a_1, a_2, a_3 的最大值 输出 101 。

这显然是矛盾的,所以 输出NG 。


入力例 3

3 2
1 1 0 11
3 3 0 1

出力例 3

OK
11 1000000000000000000 1 

对于此输入,2 第二个值可以是任何值,只要满足约束即可。


入力例 4

3 4
1 1 1 11
2 2 2 12
3 3 3 13
1 3 4 12345

出力例 4

NG

入力例 5

5 6
1 3 4 7
3 5 7 14
2 4 -10 4
2 4 3 7
1 2 1 6
4 5 -10 2

出力例 5

OK
1 3 3 7 5