大学附近有一个公交车站。课程结束了,n个学生停了下来。第 i 个学生将在时间 ti 出现在公交车站(所有 ti 都是不同的)。
我们假设停靠点位于坐标轴 Ox 上,在点 x = 0 处,并且公交车沿射线 Ox 行驶,即朝坐标轴的正方向行驶,然后返回。第 i 个学生需要到达坐标为 xi (xi > 0) 的点。
公交车按照以下算法移动。最初它位于点 0。学生们不断地来到车站并上车。公共汽车的座位容量等于 m 名乘客。当m个学生上车的那一刻,车就开始向坐标轴正方向移动。当最后(第 n)名学生上车时,它也开始移动。公交车以每 1 单位时间 1 单位距离的速度移动,即在时间 y 内行驶距离 y。
每当公交车经过至少一名学生需要下车的地点时,它就会停下来,让这些学生下车。学生需要 1 + [k / 2] 单位的时间才能下车,其中 k 是此时离开的学生人数。表达式[k / 2]表示向下取整k / 2。当最后一个学生离开巴士时,巴士掉头返回到点x = 0。直到到达该点才停止。在给定的时间点,公交车上再次挤满了学生,一切都重复了。
如果学生在没有公交车的情况下到达车站,他们会排成一队并按照来的顺序上车。任何数量的学生在可以忽略不计的时间内上车,你应该假设这不需要任何时间。任何其他行动也不需要时间。巴士上除了学生外没有其他乘客。
编写一个程序来确定每个学生下车的时间。学生下车的时刻是公交车停在学生的目的地站的时刻(尽管事实上这群学生需要一些时间才能下车)。
输入
第一行包含两个空格分隔的整数 n, m (1 ≤ n, m ≤ 105) — 相应的学生人数和公交车可以运送的乘客人数。接下来的 n 行包含对学生的描述,每行一个。每行包含一对整数 ti, xi (1 ≤ ti ≤ 105, 1 ≤ xi ≤ 104)。这些行按照 ti 严格递增的顺序给出。 xi 的值可以重合。
输出
打印 n 个数字 w1, w2, ..., wn, wi — 第 i 个学生下车的时刻。将数字打印在一行上,并用单个空格分隔。
示例
输入 #1
1 10 3 5
输出 #1
8
输入 #2
2 1 3 5 4 5
输出 #2
8 19
输入 #3
5 4 3 5 4 5 5 5 6 5 7 1
输出 #3
11 11 11 11 20
输入#4
20 4 28 13 31 13 35 6 36 4 52 6 53 4 83 2 84 4 87 1 93 6 108 4 113 6 116 1 125 2 130 2 136 13 162 2 166 4 184 1 192 2
输出#4
51 51 43 40 93 89 86 89 114 121 118 121 137 139 139 152 195 199 193 195
注意
在第一个示例中,公共汽车等待第一个学生 3 个单位的时间,并用另外 5 个单位的时间将他送到目的地。所以学生在时间 3 + 5 = 8 的时刻离开了公共汽车。
在第二个样本中,公共汽车的容量等于 1,这就是为什么它将单独驾驶第一个学生。该学生与第一个样本中的学生相同。因此,公共汽车在时间 8 到达目的地,花费 1 + [1 / 2] = 1 单位时间让他下车,并在另外 5 单位时间内返回到 0。即,公交车在时刻14返回公交车站。此时第二个学生已经来到公交车站。于是他立即上车,又多花了 5 个单位的时间到达目的地。他此时到达那里 14 + 5 = 19。
在第三个样本中,公交车等待第四个学生 6 个单位的时间,然后行驶 5 个单位的时间,然后让乘客下车 1 + [4 / 2] = 3 个单位的时间,然后返回 5 个单位的时间,然后驾驶第五个学生 1 个单位的时间。