問題文

ニコニコテレビちゃんは、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} の最大値を出力する。

コンテスト前日、ニコニコテレビちゃんはしっかり準備を終わらせ就寝しました。 当日の朝起きると、あら大変、パソコンが完全に壊れていました。

ニコニコテレビちゃんは頑張ってデータを復元したのですが、 数列の初期値 a_1,\ a_2,\ ...,\ a_N だけ復元することが出来ませんでした。

しかしニコニコテレビちゃんは、この逆境を逆手に取り、新たな問題を生み出すことに成功しました。 それは、この数列 a_1,\ a_2,\ ...,\ a_N を復元する、という問題です。

ここからが今回の問題です。

N と Q と クエリの内容 l_i,\ r_i,\ x_i、そしてその出力 y_i が与えられます。

あなたは、元の数列 a_1,\ a_2,\ ...,\ a_N としてあり得るものが存在するかを判定し、存在する場合はそれを 1 つ出力してください。

ただし、ニコニコテレビちゃんは 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

入力例 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