CF172C Bus

大学附近有一个公交站。下课后，有 $n$ 名学生来到公交站。第 $i$ 位学生将在时刻 $t_{i}$ 到达公交站（所有的 $t_{i}$ 互不相同）。 假设公交站位于坐标轴 $Ox$ 上的点 $x=0$，公交车沿着 $Ox$ 正方向行驶，然后再返回。第 $i$ 位学生需要到达坐标为 $x_{i}$ 的点（$x_{i}>0$）。 公交车按照如下规则运行：初始时在 $0$ 点。学生们陆续到达车站并上车。当有 $m$ 名学生上车时，公交车就会立即向正方向出发。若所有学生都已上车（即第 $n$ 位学生也上车后），则无论车上是否坐满，公交车也会发车。公交车的速度为 $1$ 单位距离每单位时间，即走距离 $y$ 需要 $y$ 单位时间。 每当公交车经过某个有学生需要下车的地点时，都要停下来让这些学生下车。下车需要 $1+\left\lfloor k/2\right\rfloor$ 个单位时间，其中 $k$ 为在该点下车的学生人数（$\left\lfloor k/2\right\rfloor$ 表示 $k/2$ 向下取整）。一旦最后一名学生下车，公交车立即掉头原路返回出发点 $x=0$，中途不再停车。返回 $x=0$ 后，下一批学生上车并重复上述流程。 如果学生抵达公交站但车还没来，他们在车站排队，按到达顺序依次上车。所有学生上车的耗时可忽略不计，你可以认为完全不需要时间。其它动作同样可以假定无需耗时。公交车上除了学生没有其他乘客。 请编写程序，计算每个学生下车的具体时间。学生下车的时刻定义为公交车抵达他目的地停车的那一刻（无论有几人下车，时间指公交到站停车的时刻）。

第一行包含两个用空格分隔的整数 $n,m$（$1\leq n,m\leq 10^{5}$）——学生人数以及公交车的最大载客数。接下来 $n$ 行，每行包含两个整数 $t_{i},x_{i}$（$1\leq t_{i}\leq 10^{5},1\leq x_{i}\leq 10^{4}$），按照严格递增的 $t_{i}$ 顺序给出。$x_{i}$ 值可以重复。

输出 $n$ 个数字 $w_{1},w_{2},...,w_{n}$，其中 $w_{i}$ 表示第 $i$ 位学生下车的时间。按顺序输出，数字之间用空格隔开。

在第一个样例中，公交车会等待第一位学生 $3$ 单位时间，然后再用 $5$ 单位时间送他到目的地。所以该学生在 $3+5=8$ 时刻下车。 在第二个样例中，公交车载客量为 $1$，因此只能带第一位学生，他在 $8$ 时刻到达目的地，下车用 $1+\left\lfloor1/2\right\rfloor=1$ 单位时间，返回起点用 $5$ 单位时间，总共在 $14$ 时刻返回车站。此时第二位学生已到达，可以立刻上车，前往目的地需 $5$ 单位时间，在 $14+5=19$ 时刻到达终点。 在第三个样例中，公交车会等待到第 $4$ 位学生到达（等待 $6$ 个单位时间），然后用 $5$ 单位时间抵达目的地，下客 $1+\left\lfloor 4/2\right\rfloor=3$ 单位时间，再用 $5$ 单位时间返回，然后第 $5$ 位学生上车，前往目的地用 $1$ 单位时间。 由 ChatGPT 5 翻译