CF257E.Greedy Elevator

The m-floor (m > 1) office of international corporation CodeForces has the advanced elevator control system established. It works as follows.

All office floors are sequentially numbered with integers from 1 to m. At time t = 0, the elevator is on the first floor, the elevator is empty and nobody is waiting for the elevator on other floors. Next, at times t__i (t__i > 0) people come to the elevator. For simplicity, we assume that one person uses the elevator only once during the reported interval. For every person we know three parameters: the time at which the person comes to the elevator, the floor on which the person is initially, and the floor to which he wants to go.

The movement of the elevator between the floors is as follows. At time t (t ≥ 0, t is an integer) the elevator is always at some floor. First the elevator releases all people who are in the elevator and want to get to the current floor. Then it lets in all the people waiting for the elevator on this floor. If a person comes to the elevator exactly at time t, then he has enough time to get into it. We can assume that all of these actions (going in or out from the elevator) are made instantly. After that the elevator decides, which way to move and at time (t + 1) the elevator gets to the selected floor.

The elevator selects the direction of moving by the following algorithm.

• If the elevator is empty and at the current time no one is waiting for the elevator on any floor, then the elevator remains at the current floor.
• Otherwise, let's assume that the elevator is on the floor number x (1 ≤ x ≤ m). Then elevator calculates the directions' "priorities" p__up and p__down: p__up is the sum of the number of people waiting for the elevator on the floors with numbers greater than x, and the number of people in the elevator, who want to get to the floors with the numbers greater than x; p__down is the sum of the number of people waiting for the elevator on the floors with numbers less than x, and the number of people in the elevator, who want to get to the floors with the numbers less than x. If p__up ≥ p__down, then the elevator goes one floor above the current one (that is, from floor x to floor x + 1), otherwise the elevator goes one floor below the current one (that is, from floor x to floor x - 1).

Your task is to simulate the work of the elevator and for each person to tell the time when the elevator will get to the floor this person needs. Please note that the elevator is large enough to accommodate all the people at once.

国际公司 CodeForces 的 m 层（m > 1）办公楼配备了先进的电梯控制系统，其工作方式如下。

所有办公楼层按整数顺序编号，从 1 到 m。在时刻 t = 0，电梯位于第 1 层，此时电梯为空，且其他楼层均无人等候电梯。随后，在时刻 t__i（t__i > 0）有人到达电梯。为简化问题，我们假设每个人在所报告的时间区间内仅使用一次电梯。对每个人，我们知道三个参数：其到达电梯的时刻、其初始所在楼层、以及其希望前往的目标楼层。

电梯在各楼层之间的运行规则如下：在时刻 t（t ≥ 0，且 t 为整数），电梯总位于某一楼层。首先，电梯释放所有已在电梯内且目标楼层即为当前楼层的乘客；接着，允许所有正在该楼层等候电梯的乘客进入电梯。若某人在恰好时刻 t 到达电梯，则他有足够时间进入电梯。我们假设所有进出电梯的动作均瞬间完成。此后，电梯决定移动方向，并于时刻 (t + 1) 到达所选楼层。

电梯依据以下算法确定移动方向：

• 若电梯为空，且当前时刻没有任何人在任何楼层等候电梯，则电梯保持静止，停留在当前楼层；
• 否则，设电梯当前位于楼层 x（1 ≤ x ≤ m）。电梯计算“上行优先级” p__up 和“下行优先级” p__down：
  p__up 等于所有楼层编号大于 x 的楼层上等候电梯的人数，加上电梯内所有目标楼层编号大于 x 的乘客人数；
  p__down 等于所有楼层编号小于 x 的楼层上等候电梯的人数，加上电梯内所有目标楼层编号小于 x 的乘客人数。
  若 p__up ≥ p__down，则电梯向上移动一层（即从楼层 x 移至楼层 x + 1）；否则，电梯向下移动一层（即从楼层 x 移至楼层 x − 1）。

你的任务是模拟该电梯的运行过程，并对每位乘客，输出电梯抵达其目标楼层的时刻。请注意，电梯容量足够大，可同时容纳所有乘客。

The first line contains two space-separated integers: n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 105) — the number of people and floors in the building, correspondingly.

Next n lines each contain three space-separated integers: t__i, s__i, f__i (1 ≤ t__i ≤ 109, 1 ≤ s__i, f__i ≤ m, s__i ≠ f__i) — the time when the i-th person begins waiting for the elevator, the floor number, where the i-th person was initially located, and the number of the floor, where he wants to go.

第一行包含两个用空格分隔的整数：$n$、$m$（$1 ≤ n ≤ 10^5$，$2 ≤ m ≤ 10^5$），分别表示楼内人数和楼层数。

接下来的 $n$ 行，每行包含三个用空格分隔的整数：$t_i$、$s_i$、$f_i$（$1 ≤ t_i ≤ 10^9$，$1 ≤ s_i, f_i ≤ m$，$s_i ≠ f_i$），分别表示第 $i$ 个人开始等待电梯的时间、其初始所在楼层编号以及其希望前往的楼层编号。

Print n lines. In the i-th line print a single number — the moment of time, when the i-th person gets to the floor he needs. The people are numbered in the order, in which they are given in the input.

Please don't use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出 n 行。在第 i 行中输出一个整数——即第 i 个人到达其目标楼层的时刻。人员编号顺序与其在输入中给出的顺序一致。

请勿在 C++ 中使用 %lld 格式说明符读写 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。

In the first sample the elevator worked as follows:

• t = 1. The elevator is on the floor number 1. The elevator is empty. The floor number 2 has one person waiting. p__up = 1 + 0 = 1, p__down = 0 + 0 = 0, p__up ≥ p__down. So the elevator goes to the floor number 2.
• t = 2. The elevator is on the floor number 2. One person enters the elevator, he wants to go to the floor number 7. p__up = 0 + 1 = 1, p__down = 0 + 0 = 0, p__up ≥ p__down. So the elevator goes to the floor number 3.
• t = 3. The elevator is on the floor number 3. There is one person in the elevator, he wants to go to floor 7. The floors number 4 and 6 have two people waiting for the elevator. p__up = 2 + 1 = 3, p__down = 0 + 0 = 0, p__up ≥ p__down. So the elevator goes to the floor number 4.
• t = 4. The elevator is on the floor number 4. There is one person in the elevator who wants to go to the floor number 7. One person goes into the elevator, he wants to get to the floor number 8. The floor number 6 has one man waiting. p__up = 1 + 2 = 3, p__down = 0 + 0 = 0, p__up ≥ p__down. So the elevator goes to the floor number 5.
• t = 5. The elevator is on the floor number 5. There are two people in the elevator, they want to get to the floors number 7 and 8, correspondingly. There is one person waiting for the elevator on the floor number 6. p__up = 1 + 2 = 3, p__down = 0 + 0 = 0, p__up ≥ p__down. So the elevator goes to the floor number 6.
• t = 6. The elevator is on the floor number 6. There are two people in the elevator, they want to get to the floors number 7 and 8, correspondingly. One man enters the elevator, he wants to get to the floor number 5. p__up = 0 + 2 = 2, p__down = 0 + 1 = 1, p__up ≥ p__down. So the elevator goes to the floor number 7.
• t = 7. The elevator is on the floor number 7. One person leaves the elevator, this person wanted to get to the floor number 7. There are two people in the elevator, they want to get to the floors with numbers 8 and 5, correspondingly. p__up = 0 + 1 = 1, p__down = 0 + 1 = 1, p__up ≥ p__down. So the elevator goes to the floor number 8.
• t = 8. The elevator is on the floor number 8. One person leaves the elevator, this person wanted to go to the floor number 8. There is one person in the elevator, he wants to go to the floor number 5. p__up = 0 + 0 = 0, p__down = 0 + 1 = 1, p__up < p__down. So the elevator goes to the floor number 7.
• t = 9. The elevator is on the floor number 7. There is one person in the elevator, this person wants to get to the floor number 5. p__up = 0 + 0 = 0, p__down = 0 + 1 = 1, p__up < p__down. So the elevator goes to the floor number 6.
• t = 10. The elevator is on the floor number 6. There is one person in the elevator, he wants to get to the floor number 5. p__up = 0 + 0 = 0, p__down = 0 + 1 = 1, p__up < p__down. So the elevator goes to the floor number 5.
• t = 11. The elevator is on the floor number 5. One person leaves the elevator, this person initially wanted to get to the floor number 5. The elevator is empty and nobody needs it, so the elevator remains at the floor number 5.

在第一个样例中，电梯的工作过程如下：

• $t = 1$：电梯位于第 1 层。电梯为空。第 2 层有 1 人正在等待。$p_{\text{up}} = 1 + 0 = 1$，$p_{\text{down}} = 0 + 0 = 0$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 2 层。
• $t = 2$：电梯位于第 2 层。1 人进入电梯，此人欲前往第 7 层。$p_{\text{up}} = 0 + 1 = 1$，$p_{\text{down}} = 0 + 0 = 0$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 3 层。
• $t = 3$：电梯位于第 3 层。电梯内有 1 人，欲前往第 7 层。第 4 层和第 6 层共有 2 人正在等待电梯。$p_{\text{up}} = 2 + 1 = 3$，$p_{\text{down}} = 0 + 0 = 0$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 4 层。
• $t = 4$：电梯位于第 4 层。电梯内有 1 人，欲前往第 7 层。1 人进入电梯，此人欲前往第 8 层。第 6 层有 1 人正在等待。$p_{\text{up}} = 1 + 2 = 3$，$p_{\text{down}} = 0 + 0 = 0$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 5 层。
• $t = 5$：电梯位于第 5 层。电梯内有 2 人，分别欲前往第 7 层和第 8 层。第 6 层有 1 人正在等待电梯。$p_{\text{up}} = 1 + 2 = 3$，$p_{\text{down}} = 0 + 0 = 0$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 6 层。
• $t = 6$：电梯位于第 6 层。电梯内有 2 人，分别欲前往第 7 层和第 8 层。1 人进入电梯，此人欲前往第 5 层。$p_{\text{up}} = 0 + 2 = 2$，$p_{\text{down}} = 0 + 1 = 1$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 7 层。
• $t = 7$：电梯位于第 7 层。1 人离开电梯（此人原计划前往第 7 层）。电梯内剩余 2 人，分别欲前往第 8 层和第 5 层。$p_{\text{up}} = 0 + 1 = 1$，$p_{\text{down}} = 0 + 1 = 1$，$p_{\text{up}} \ge p_{\text{down}}$。因此电梯前往第 8 层。
• $t = 8$：电梯位于第 8 层。1 人离开电梯（此人原计划前往第 8 层）。电梯内剩余 1 人，欲前往第 5 层。$p_{\text{up}} = 0 + 0 = 0$，$p_{\text{down}} = 0 + 1 = 1$，$p_{\text{up}} < p_{\text{down}}$。因此电梯前往第 7 层。
• $t = 9$：电梯位于第 7 层。电梯内有 1 人，欲前往第 5 层。$p_{\text{up}} = 0 + 0 = 0$，$p_{\text{down}} = 0 + 1 = 1$，$p_{\text{up}} < p_{\text{down}}$。因此电梯前往第 6 层。
• $t = 10$：电梯位于第 6 层。电梯内有 1 人，欲前往第 5 层。$p_{\text{up}} = 0 + 0 = 0$，$p_{\text{down}} = 0 + 1 = 1$，$p_{\text{up}} < p_{\text{down}}$。因此电梯前往第 5 层。
• $t = 11$：电梯位于第 5 层。1 人离开电梯（此人原计划前往第 5 层）。此时电梯为空，且无人需要乘坐电梯，因此电梯停留在第 5 层。