Problem Description

Nico Nico TV-chan was preparing a problem for the programming contest hosted by dwango, "The Challenge from Dwango". The problem was as follows:

• Given a sequence of length $ N $, $a_1,\ a_2,\ ...,\ a_N$, process $ Q $ queries.
• For the $ i $-th query, $l_i,\ r_i,\ x_i$ are given, and the following process is performed:
• Add $ x_i $ to each of $a_{l_i},\ a_{l_i+1},\ ...,\ a_{r_i}$. Then, output the maximum value of $a_{l_i},\ a_{l_i+1},\ ...,\ a_{r_i}$.

The day before the contest, Nico Nico TV-chan finished preparing and went to sleep. When she woke up the next morning, she found her computer completely broken.

Nico Nico TV-chan managed to recover the data, but she could only restore the initial values of the sequence $a_1,\ a_2,\ ...,\ a_N$.

However, Nico Nico TV-chan turned this adversity into an opportunity and successfully created a new problem. It was a problem to restore the sequence $a_1,\ a_2,\ ...,\ a_N$.

Here is the problem for today:

Given $ N $, $ Q $, the content of the queries $l_i,\ r_i,\ x_i$, and the outputs $ y_i $, determine if there exists a possible original sequence $a_1,\ a_2,\ ...,\ a_N$ and, if it exists, output one such sequence.

Note that Nico Nico TV-chan remembers that $a_1,\ a_2,\ ...,\ a_N$ were all integers and their absolute values were within $ 10^{18} $. So, make sure your output satisfies this constraint.

For all the test cases provided, whether the constraint on the values of $a_1,\ a_2,\ ...,\ a_N$ exists or not, it is guaranteed that the existence of a possible original sequence does not change.

Input Format

The input is given from the standard input in the following format:

$ 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 $

Output Format

If there is no sequence $ a_i $ that satisfies the conditions, output NG.

If it exists, output OK and on the next line, output $a_1,\ a_2,\ ...,\ a_N$ separated by spaces in order.

Sample Input and Output

Sample Input #1

3 1
1 3 100 300

Sample Output #1

OK
200 200 200

Sample Input #2

3 2
1 3 0 100
1 3 0 101

Sample Output #2

NG

Sample Input #3

3 2
1 1 0 11
3 3 0 1

Sample Output #3

OK
11 1000000000000000000 1

Sample Input #4

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

Sample Output #4

NG

Sample Input #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

Sample Output #5

OK
1 3 3 7 5

Notes/Hints

Constraints

• All inputs are integers.
• $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

After adding $ 100 $, the maximum value of $a_1,\ a_2,\ a_3$ is $ 300 $, so for example, $200,\ 200,\ 200$ satisfies the condition.

Sample Explanation 2

In this case, the first query outputs the maximum value of $a_1,\ a_2,\ a_3$ as $ 100 $, and the second query outputs it as $ 101 $. This is clearly contradictory, so output NG.

Sample Explanation 3

For this input, the second value can be anything as long as it satisfies the constraint.

见题面 Input 部分

见题面 Output 部分