← 返回题目列表

Codeforces · 117/A

A. 电梯

中文机器翻译题面 查看原题

现在,俄罗斯最负盛名的比赛之一——俄罗斯 Codec 杯的众多资格赛已经结束。所有进入决赛的n名参赛者都发现自己身处一个巨大的m层108星级酒店。来到这样的地方,第一个想法当然是“去看看电梯怎么样?”。

酒店的电梯按照一种不变的方案在楼层之间移动。最初(在时间 0 时刻)电梯位于 1 层,然后移动到 2 层,然后移动到 3 层,依此类推,直到到达 m 层。之后电梯移动到 m-1 层,然后移动到 m-2 层,以此类推,直到到达一楼。这个过程无限重复。我们知道电梯的载客量是无限的;我们还知道,在每个楼层,人们都会立即登上电梯。在楼层之间移动需要一个时间单位。

对于 n 个参与者中的每一个,您都会获得 si(代表第 i 个参与者开始的楼层)、fi(代表第 i 个参与者想要到达的楼层)和 ti(代表第 i 个参与者在楼层 si 开始的时间)。

对于每个参与者,请打印他/她到达楼层的最短时间 fi。

如果电梯在ti时刻停在si层,则第i个参与者可以立即进入电梯。如果参与者从楼层 si 开始,并且这是他最初想要到达的楼层 (si = fi),则该参与者到达楼层 fi 的时间被认为等于 ti。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 105, 2 ≤ m ≤ 108)。

接下来的 n 行包含有关参与者的信息,其形式为三个空格分隔的整数 si fi ti (1 ≤ si, fi ≤ m, 0 ≤ ti ≤ 108),如问题陈述中所述。

输出

打印 n 行,每行包含一个整数 — 每个参与者到达所需楼层的时间。

示例

输入 #1

7 4
2 4 3
1 2 0
2 2 0
1 2 1
4 3 5
1 2 2
4 2 0

输出 #1

9
1
0
7
10
7
5

输入 #2

5 5
1 5 4
1 3 1
1 3 4
3 1 5
4 2 5

输出 #2

12
10
10
8
7

注意

让我们考虑第一个示例。第一个参与者在时间等于 t = 3 时从 s = 2 层开始。要到达 f = 4 层,他必须等到时间等于 7,即电梯第二次向上运行的时间。然后第一个参与者应该乘电梯并上两层楼。在这种情况下,第一个参与者在时间等于 9 时到达楼层 f。第二个参与者在时间 t = 0 时从楼层 s = 1 出发,立即进入电梯,并到达楼层 f = 2。第三个参与者不需要等待电梯,因为他需要到达他出发的同一楼层。