CF257E Greedy Elevator

国际公司 CodeForces 的 $m$ 层（$m > 1$）办公楼配备了先进的电梯控制系统。其工作原理如下： 所有办公楼层从 $1$ 到 $m$ 顺序编号。在初始时刻 $t=0$，电梯位于第 $1$ 层，电梯内无人，且其它楼层也没有人在等电梯。接下来，在时刻 $t_{i}$（$t_{i}>0$）会有人来乘坐电梯。为简化起见，假设每个人在这个时间段内只使用一次电梯。对于每个人，已知三项参数：其到达电梯的时间、初始所在楼层和想要到达的楼层。 电梯在楼层间的移动规则如下：在任意时刻 $t$（$t\ge0$ 且 $t$ 为整数），电梯总在某一楼层。首先，电梯会让所有目标楼层为当前楼层的乘客下电梯；接着让该楼层所有等电梯的人进入电梯。如果某人在恰好 $t$ 时刻到达，则他有足够时间进电梯。我们可以认为所有上下电梯的行为都是瞬间完成的。之后电梯决定移动方向，并在时刻 $t+1$ 到达所选择的楼层。 电梯按照以下算法选择移动方向： - 如果电梯为空，且当前时刻没有人在任意楼层等电梯，则电梯停留在本楼层。 - 否则，假设电梯当前在 $x$ 楼（$1\le x\le m$）。此时电梯计算两个方向的“优先级” $p_{up}$ 和 $p_{down}$：$p_{up}$ 为大于 $x$ 楼的所有等电梯人数与当前电梯内目标楼层大于 $x$ 的人数之和；$p_{down}$ 为小于 $x$ 楼的所有等电梯人数与当前电梯内目标楼层小于 $x$ 的人数之和。如果 $p_{up} \ge p_{down}$，则电梯上行到 $x+1$ 层，否则下行到 $x-1$ 层。 你的任务是模拟电梯的运行，并输出每个人到达目标楼层的时刻。注意：电梯足够大，可容纳所有人。

第一行包含两个用空格分隔的整数 $n$ 和 $m$，分别表示大楼里的人数和楼层数（$1\le n\le10^{5},\;2\le m\le10^{5}$）。 接下来的 $n$ 行，每行包含三个用空格分隔的整数 $t_{i},s_{i},f_{i}$（$1 \le t_{i} \le 10^{9},\ 1 \le s_{i},f_{i} \le m,\ s_{i}\neq f_{i}$），表示第 $i$ 个人到达电梯的时刻、所处楼层和想要到达的楼层。

输出 $n$ 行，第 $i$ 行输出一个整数，表示第 $i$ 个人到达目标楼层的时刻。按照输入顺序输出。 请不要在 C++ 中使用 %lld 读写 64 位整数，建议使用 cin、cout 流或 %I64d。

第一个样例中，电梯的运行过程如下： - $t=1$。电梯在 $1$ 层，电梯内没人。$2$ 层有一个人在等电梯。$p_{up}=1+0=1$，$p_{down}=0+0=0$，$p_{up}\ge p_{down}$，电梯上行到 $2$ 层。 - $t=2$。电梯在 $2$ 层，有一人进电梯，目标 $7$ 层。$p_{up}=0+1=1$，$p_{down}=0+0=0$，$p_{up}\ge p_{down}$，电梯上行到 $3$ 层。 - $t=3$。电梯在 $3$ 层，有一人目标 $7$ 层。$4$、$6$ 层各有一人等电梯。$p_{up}=2+1=3$，$p_{down}=0+0=0$，$p_{up}\ge p_{down}$，电梯上行到 $4$ 层。 - $t=4$。电梯在 $4$ 层，一人目标 $7$ 层。有一人进电梯，目的 $8$ 层。$6$ 层有一人在等。$p_{up}=1+2=3$，$p_{down}=0+0=0$，$p_{up}\ge p_{down}$，电梯上行到 $5$ 层。 - $t=5$。电梯在 $5$ 层，两人目标 $7$、$8$ 层。$6$ 层有一人在等。$p_{up}=1+2=3$，$p_{down}=0+0=0$，$p_{up}\ge p_{down}$，电梯上行到 $6$ 层。 - $t=6$。电梯在 $6$ 层，两人目标 $7$、$8$ 层。一人进电梯，目标 $5$ 层。$p_{up}=0+2=2$，$p_{down}=0+1=1$，$p_{up}\ge p_{down}$，电梯上行到 $7$ 层。 - $t=7$。电梯在 $7$ 层，一人下电梯，此人目标 $7$ 层。电梯内剩两人目标 $8$ 和 $5$ 层。$p_{up}=0+1=1$，$p_{down}=0+1=1$，$p_{up}\ge p_{down}$，电梯上行到 $8$ 层。 - $t=8$。电梯在 $8$ 层，一人下电梯，目标 $8$ 层。电梯内剩一人目标 $5$ 层。$p_{up}=0+0=0$，$p_{down}=0+1=1$，$p_{up}