问题描述

Nico Nico Television Chan 准备了一个由 Dwango 主办的编程竞赛的问题，这个问题是关于以下内容的。

• 给定一个长度为 N 的数列 a1, a2, ..., aN，对其进行 Q 个查询处理
• 第 i 个查询中给定 li, ri, xi，并进行以下操作
• 对 a[li], a[li+1], ..., a[ri] 分别加上 xi，然后输出 a[li], a[li+1], ..., a[ri] 的最大值。

比赛前一天晚上，Nico Nico Television Chan 做好了充分的准备并且就寝。当她在第二天早上醒来时，遇到了一个大问题，电脑完全坏了。

尽管 Nico Nico Television Chan 努力恢复数据，但她只能恢复数列的初始值 a1, a2, ..., aN。

然而 Nico Nico Television Chan 利用逆境成功地提出了一个新问题。那就是恢复这个数列 a1, a2, ..., aN。

下面是本次问题的内容。

给定 N、Q、查询的内容 li, ri, xi，以及输出 yi。

你需要判断是否存在原始数列 a1, a2, ..., aN，并输出其中一个。

注意，Nico Nico Television Chan 记得 a1, a2, ..., aN 都是整数，并且绝对值不超过 $10^{18}$。因此，请确保输出满足这个约束条件。

此外，对于提供的所有测试用例，即使 a1, a2, ..., aN 的值存在约束条件或不存在约束条件，原始数列是否存在都是保证不变的。

约束条件

• 输入都是整数。
• $1 \leq N \leq 200,000$
• $1 \leq Q \leq 200,000$
• $1 \leq li \leq ri \leq N$
• $|xi| \leq 10^9$
• $|yi| \leq 10^9$

---

输入

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

N Q l1 r1 x1 y1 l2 r2 x2 y2 : lq rq xq yq

输出

如果不存在满足条件的数列 ai，则输出 NG。

如果存在，则输出 OK，接下来一行按顺序用空格分隔输出 a1, a2, ..., aN。

---

示例 1

输入示例：

3 1
1 3 100 300

输出示例：

OK
200 200 200

因为将 100 加到 a1, a2, a3 后的最大值为 300，例如 200, 200, 200 就满足条件。

---

示例 2

输入示例：

3 2
1 3 0 100
1 3 0 101

输出示例：

NG

在这个案例中，第一个查询输出 a1, a2, a3 的最大值为 100，第二个查询输出 a1, a2, a3 的最大值为 101。

这显然是矛盾的，因此输出 NG。

---

示例 3

输入示例：

3 2
1 1 0 11
3 3 0 1

输出示例：

OK
11 1000000000000000000 1

在本次输入中，第二个值可以是任何满足约束条件的值。

---

示例 4

输入示例：

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

输出示例：

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

输出示例：

OK
1 3 3 7 5