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

[problemUrl]: https://atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_d ニコニコテレビちゃんは、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 $ の値の制約があってもなくても、 元の数列としてあり得るものが存在するかどうかは変わらないことが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ 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\ ≦\ N\ ≦\ 200,000 $ - $ 1\ ≦\ Q\ ≦\ 200,000 $ - $ 1\ ≦\ l_i\ ≦\ r_i\ ≦\ N $ - $ |x_i|\ ≦\ 10^9 $ - $ |y_i|\ ≦\ 10^9 $ ### Sample Explanation 1 $ 100 $ を足した後の $ a_1,\ a_2,\ a_3 $ の最大値が $ 300 $ ということなので、例えば $ 200,\ 200,\ 200 $ が条件を満たします。 ### Sample Explanation 2 このケースでは、 $ 1 $ つ目のクエリでは $ a_1,\ a_2,\ a_3 $ の最大値を $ 100 $ と出力して、 $ 2 $ つ目のクエリでは $ a_1,\ a_2,\ a_3 $ の最大値を $ 101 $ と出力しています。 これは明らかに矛盾しているため、`NG` と出力します。 ### Sample Explanation 3 今回の入力ならば、$ 2 $ つ目の値は制約を満たしていればなんでもよいです。