现在,俄罗斯最负盛名的比赛之一——俄罗斯 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。第三个参与者不需要等待电梯,因为他需要到达他出发的同一楼层。