Fault Layers

This problem is adapted from T5 "Fault" of the JOI 2016 Final. In an ancient advanced civilization called IOI, the ground was originally flat and layered. In the original setup, at a years before the civilization’s extinction (a ≥ 0), the ground (or "geological surface") was the line $$y=-a$$. Therefore, the rock layer originally between $$y=-a$$ and $$y=-a+1$$ is considered to be from a years before extinction.

After the civilization’s demise, the underlying strata underwent Q tectonic movements. Each movement is described by three parameters: position X_i, direction D_i, and magnitude L_i (for i from 1 to Q). The movements are defined as follows:

• If D_i = 1: Consider a fault line passing through \((X_i,0)\) with slope 1, i.e. the line $$y=x-X_i.$$ The strata strictly above this line are shifted by the vector \((L_i, L_i)\).
• If D_i = 2: Consider a fault line passing through \((X_i,0)\) with slope -1, i.e. the line $$y=-x+X_i.$$ The strata strictly above this line are shifted by the vector \((-L_i, L_i)\).

Immediately after each tectonic movement, any part of the strata that ends up with y > 0 is eroded and lost. At the end of all tectonic movements, for each integer i from 1 to N, the rock layer between the points \((i-1,0)\) and \((i,0)\) is examined. Your task is to determine, for each segment, the original pre-extinction year of the rock layer presently occupying that segment.

How to determine the answer?

Initially, before any fault movements, the geological layers are horizontal with boundaries at \(y=0, -1, -2, \ldots\) so that the layer between \(y=-a\) and \(y=-a+1\) corresponds to the layer formed a years before extinction. The fault movements distort the layers by locally translating parts of the crust. However, these translations are rigid (only shifts) and only affect points above the respective fault lines. Thus, you can "reverse" the fault movements in reverse order to trace back the final ground point \((x,0)\) (where you may take \(x=i-0.5\) for the segment between \((i-1,0)\) and \((i,0)\)) to its original location \((x_0,y_0)\). Then, since originally the layer boundaries are at integer \(y\)-values, the pre-extinction year of the rock layer is \(\lfloor -y_0 \rfloor\) (note that \(y_0 \le 0\)).

Reverse Transformation Details:

• For a fault movement with D = 1 (fault line $$y=x-X_i$$): if the current point \((x,y)\) satisfies \(y > x-X_i\), then it was shifted and the reverse transformation is \((x,y)\) \(\to\) \((x-L_i, y-L_i)\).
• For a fault movement with D = 2 (fault line $$y=-x+X_i$$): if the current point \((x,y)\) satisfies \(y > -x+X_i\), then it was shifted and the reverse transformation is \((x,y)\) \(\to\) \((x+L_i, y-L_i)\).

Apply these reverse transformations in the reverse order of the movements (i.e. from the last movement to the first). Finally, compute \(\lfloor -y_0 \rfloor\) where \(y_0\) is the resulting y-coordinate. This value is the pre-extinction year of the rock layer.

Input Format: The first line contains two integers N and Q. The following Q lines each contain three integers X_i, D_i, and L_i describing a tectonic movement.

Output Format: Output N lines. The i^th line (1 ≤ i ≤ N) should contain the pre-extinction year (an integer) of the rock layer between the points \((i-1,0)\) and \((i,0)\).

inputFormat

The input is given as follows:

N Q
X1 D1 L1
X2 D2 L2
... (Q lines in total)

Where:

• 1 ≤ N ≤ (some large number)
• Q is the number of tectonic movements
• For each movement: D_i is either 1 or 2.

outputFormat

Output N lines. The i^th line should contain a single integer representing the pre-extinction year of the rock layer that is now located between \((i-1,0)\) and \((i,0)\).

sample

3 1
1 1 1

1
0
0

</p>