Water Flow Sensor Activation

You are given a horizontal pipe of length (len) (divided into (len) unit segments). Each segment contains a valve (with an on/off switch) and a water flow sensor located at its center. Initially, the pipe is empty. For each valve event, the valve at position (L_i) is opened at time (S_i) and continuously allows water into the pipe. Then, at time (T_i) (with (T_i \ge S_i)), the water flowing in from this valve causes the sensors in segments from (L_i - (T_i - S_i)) to (L_i + (T_i - S_i)) (inclusive) to detect water flow.

Your task is to determine, for each segment, the earliest time its sensor detects water flow. It is guaranteed that every sensor will eventually detect water flow.

Note: All formulas are given in LaTeX format.

inputFormat

The first line contains two integers (len) and (n), where (len) is the number of segments in the pipe and (n) is the number of valve events. Each of the next (n) lines contains three integers (L_i), (S_i), and (T_i), representing that the valve at segment (L_i) is opened at time (S_i) and at time (T_i) the water from this valve covers segments from (L_i - (T_i - S_i)) to (L_i + (T_i - S_i)).

outputFormat

Output (len) integers separated by a space, where the (j)-th integer is the earliest time when the sensor at segment (j) detects water flow.

sample

5 1
3 2 4

4 4 4 4 4