Fault

Long ago the IOI civilisation flourished, then a volcanic eruption destroyed it. The civilisation grew along a straight river, and when it fell its ground surface was perfectly flat.

Treat the ruins as a coordinate plane. The $x$ axis is the ground surface and the $y$ axis is the height direction. The line $y = 0$ is the surface, the region $y > 0$ is above ground, and the region $y < 0$ is underground. Measured from the moment the civilisation fell, the layer deposited $a$ years earlier ($a \ge 0$) lay on the line $y = -a$.

After the fall, $Q$ crustal movements happened at the ruins. The $i$th movement ($1 \le i \le Q$) is described by a position $X_i$, a direction $D_i$, and an amount $L_i$, where $D_i$ is 1 or 2. The $i$th movement happens in this order.

1. The strata move.
   • If $D_i = 1$, a fault forms along the line of slope $1$ through the point $(X_i, 0)$, and the strata in the region above that line move along the line by a height of $L_i$. That is, a point $(x, y)$ above the line moves to $(x + L_i,\ y + L_i)$.
   • If $D_i = 2$, a fault forms along the line of slope $-1$ through the point $(X_i, 0)$, and the strata in the region above that line move along the line by a height of $L_i$. That is, a point $(x, y)$ above the line moves to $(x - L_i,\ y + L_i)$.
2. Immediately afterwards, every stratum lying in the region $y > 0$ is worn away and disappears.

In the present day the archaeologist Dr. JOI excavates the ruins of the IOI civilisation. He knows every crustal movement that happened, and he wants to know how many years before the fall of the civilisation each exposed layer was deposited.

Given the crustal movements, for each integer $i$ with $1 \le i \le N$, find how many years before the fall of the civilisation the layer exposed at the surface between the point $(i - 1, 0)$ and the point $(i, 0)$ was deposited.

The first line contains two integers $N$ and $Q$ separated by a space. There are $N$ layers whose ages you must report, and $Q$ crustal movements.

Each of the next $Q$ lines contains three integers. The $i$th of them ($1 \le i \le Q$) contains $X_i$, $D_i$, and $L_i$ separated by spaces, meaning that the $i$th crustal movement had position $X_i$, direction $D_i$, and amount $L_i$.

Print $N$ lines.

The $i$th line ($1 \le i \le N$) contains one integer, the number of years before the fall of the civilisation at which the layer exposed at the surface between the point $(i - 1, 0)$ and the point $(i, 0)$ was deposited.

• $1 \le N \le 200000$
• $1 \le Q \le 200000$
• $-1000000000 \le X_i \le 1000000000$ ($1 \le i \le Q$)
• $1 \le D_i \le 2$ ($1 \le i \le Q$)
• $1 \le L_i \le 1000000000$ ($1 \le i \le Q$)