P5103 [JOI 2016 Final] Fault / Geologic Fault

**The translator’s ability is limited; I sincerely ask everyone to provide a better translation.** **This problem is translated from [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T5 “[断層](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)”.** A very long time ago, an advanced civilization called IOI flourished. As time passed, the modern archaeologist Dr. JOI decided to excavate the ruins of the IOI civilization. The IOI civilization developed along a straight river. For convenience, the ruins of the IOI civilization can be regarded as the $x$ axis of the Cartesian coordinate plane, and the $y$ axis represents altitude. The ground surface of the IOI civilization is flat; that is, the line $y=0$ represents the ground, $y>0$ is above the ground, and $y0$ disappear due to weathering. You are asked: for each $i$ $(1\leqslant i\leqslant N)$, determine **which year before the fall of the IOI civilization the stratum between point $(i-1,0)$ and point $(i,0)$ comes from**. > On the $y$ axis, every fault passes through an integer point, and there is no fault between two adjacent integer points on the $y$ axis. This should be clear, right……

The first line contains two integers $N, Q$, separated by spaces. In the next $Q$ lines, the $i$-th line $(1\leqslant i\leqslant Q)$ contains three integers $X_i, D_i, L_i$, separated by spaces. The meanings of all input values are given in the statement.

Output $N$ lines in total. The $i$-th line $(1\leqslant i\leqslant N)$ contains one integer, indicating which year before the fall of the IOI civilization the stratum between point $(i-1,0)$ and point $(i,0)$ comes from.

#### Sample Explanation 1  #### Constraints and Notes For all testdata, $1\leqslant N, Q\leqslant 2\times 10^5$, $-10^9\leqslant X_i\leqslant 10^9$, $D_i=1$ or $2$, $1\leqslant L_i\leqslant 10^9$ $(1\leqslant i\leqslant Q)$. |Subtask #|$N,Q$|Other Constraints|Score| |-|-|-|-| |1|$N,Q\leqslant 100$|$-100\leqslant X_i\leqslant 100$, $L_i=1$ $(1\leqslant i\leqslant Q)$|18| |2|$N,Q\leqslant 3000$|None.|16| |3|$N,Q\leqslant 2\times10^5$|None.|66| Translated by ChatGPT 5