配点 : 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