Construct a Non‐negative Integer Sequence under Interval Change Constraints

You are given two integers n and m. Your task is to construct a non‐negative integer sequence a of length n (i.e. a_1, a_2, ..., a_n), such that the sequence satisfies m independent constraints. The i-th constraint is defined as follows:

• If you modify the element at index x_i from a_{x_i} to y_i, then exactly k_i intervals (i.e. contiguous subarrays) will experience a change in their sum (i.e. the difference between the interval sum after the modification and the interval sum before the modification) that is at most p_i in absolute value. Formally, let T be the total number of intervals, i.e.
  \( T = \frac{n(n+1)}{2} \).
  Note that if the index x_i is not contained in an interval then that interval’s sum remains unchanged (i.e. change 0) and if it is contained then the interval sum changes by \( \delta = y_i - a_{x_i} \). Since every interval not containing x_i has a change of 0 (which is always not more than p_i provided p_i \ge 0), the constraint forces the following:

For the index x_i, let L be the number of intervals that include it. One can show that
\( L = x_i \times (n - x_i + 1) \).

Therefore, there are exactly two cases for each constraint:

1. If k_i = T, then even the intervals containing x_i must have a change no more than p_i. This forces \(|y_i - a_{x_i}| \le p_i\), i.e. a_{x_i} must lie in the closed interval \( [y_i - p_i,\; y_i + p_i]. \).
2. If k_i = T - L, then the intervals not containing x_i (which always have 0 change) are the only intervals that satisfy the condition. In other words, for those intervals that include index x_i, the change must be more than p_i in absolute value, i.e. \(|y_i - a_{x_i}| > p_i\).

These constraints are independent – the modification in one constraint does not affect another. Moreover, to prevent the sequence elements from growing excessively, if there exists any a_i > 2 \times 10^9, then the sequence is considered invalid.

Your task is to output any sequence a that satisfies all the constraints. If no valid sequence exists, output -1.

inputFormat

The first line contains two integers n and m (1 \le n \le ..., m \ge 0), representing the length of the sequence and the number of constraints.

Each of the following m lines contains four integers: x_i, y_i, k_i, p_i with 1 \le x_i \le n. These denote that if you modify a[x_i] to y_i, then exactly k_i intervals have their sum change (in absolute value) at most p_i.

outputFormat

If there exists a valid sequence, output a_1, a_2, ..., a_n in one line, separated by spaces. If there is no solution, output -1.

sample

3 1
2 5 6 2

0 3 0