电梯调度

题号：NC263974
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

红色部分在纸质题面中存在笔误，请以网页显示为准。

有一座百层大楼，楼层从 $1$ 到 $100$ 进行编号。大楼中安装了一部限载 $k$ 人的电梯，电梯可以花费 $1$ 秒钟向上或向下移动 $1$ 层。第 $0$ 秒末，电梯处于停止及空载状态，且位于第 $1$ 层。

有 $n$ 位乘客，编号从 $1$ 到 $n$ 。编号为 $i$ 的乘客于第 $t_i$ 秒初到达第 $a_i$ 层，想要前往第 $b_i$ 层。

电梯按照如下规则运行：

1. 若电梯于第 $i$ 秒末处于停止状态且位于第 $x$ 层，首先检查第 $x+1,x+2, \cdots, \color{red}{100}$ 层有没有等待的乘客，以及第 $x$ 层有没有要去 $x$ 层以上楼层的乘客。若有，则在满足载客限制的前提下尽可能接受所有需要向上的乘客，并转入向上运行状态，在第 $i+1$ 秒末到达第 $x+1$ 层。否则扫描第 $1, 2, \cdots, x - 1$ 层有没有等待的乘客，以及第 $x$ 层有没有要去 $x$ 层以下的乘客。若有，则在满足载客限制的前提下尽可能接受所有需要向下的乘客，并转入向下运行状态，在第 $i+1$ 秒末到达第 $x-1$ 层。如果仍然没有，则保持停止状态到第 $i+1$ 秒末。

2. 若电梯于第 $i$ 秒末处于向上运行状态且位于第 $x$ 层，首先检查电梯中有没有要前往第 $x$ 层的乘客，并将这些乘客在第 $i$ 秒末放下。然后扫描第 $x+1, x+2, \cdots, \color{red}{100}$ 层有没有等待的乘客，以及第 $x$ 层有没有要去 $x$ 层以上楼层的乘客。若有，则在满足载客限制的前提下，于下客完成后，在第 $i+1$ 秒初尽可能接受所有需要向上的乘客，并保持向上运行状态，在第 $i+1$ 秒末到达 $x+1$ 层。否则转入停止状态，并保持到第 $i+1$ 秒末。

3. 若电梯于第 $i$ 秒末处于向下运行状态且位于第 $x$ 层，首先检查电梯中有没有要前往第 $x$ 层的乘客，并将这些乘客在第 $i$ 秒末放下。然后扫描第 $1, 2, \cdots, x - 1$ 层有没有等待的乘客，以及第 $x$ 层有没有要去 $x$ 层以下楼层的乘客。若有，则在满足载客限制的前提下，于下客完成后，在第 $i+1$ 秒初尽可能接受所有需要向下的乘客，并保持向下运行状态，在第 $i+1$ 秒末到达 $x-1$ 层。否则转入停止状态，并保持到第 $i+1$ 秒末。

4. 若电梯于第 $i$ 秒末处于停止状态且位于第 $x$ 层，则保持停止状态到第 $i+1$ 秒末。

5. 电梯接收乘客时，会优先接收已经在该层等待最久的乘客。如果有多名等待最久的乘客，优先接受 $|a_i - b_i|$ 最小的乘客。如果仍然相同，优先接受编号最小的乘客。

请对于每位乘客，分别计算其到达目标楼层的时间为第几秒初。

输入描述:

输入的第一行为两个空格分隔的正整数  和 ，分别表示乘客的数量和电梯的限载人数。

随后  行，第  行三个空格分隔的正整数 ，，，分别表示第  位乘客的到达时间、到达楼层和目标楼层。

保证 。

输出描述:

输出一行  个空格分隔的正整数，分别表示第  位乘客到达目标楼层的时间。

示例1

输入

复制

输出

复制

3 15 4 15 21

备注:

第  秒末与第  秒初是同一时间点。