题目描述

俄罗斯最具声望的赛事之一 Russian Codec Cup 的多场资格赛落下了帷幕。闯入决赛的 $n$ 名选手都住进了一座宏伟的 $m$ 层 $10^8$ 星级酒店。在这种地方，每个人冒出的第一个念头当然是："去坐坐电梯怎么样？"

酒店的电梯按一套永不改变的方案在楼层间移动：初始时（时刻 0）电梯位于第 1 层，然后开到第 2 层，再到第 3 层……如此继续，直到到达第 $m$ 层。之后电梯开到第 $m-1$ 层，再到 $m-2$ 层……直到回到第 1 层。这个过程无限重复。电梯容量无限，且每层的人一到就立刻上电梯。电梯在相邻楼层间移动花费一个单位时间。

对 $n$ 名选手中的每一个人，给定：$s_i$（第 $i$ 名选手出发的楼层）、$f_i$（他想到达的楼层）、$t_i$（他出现在楼层 $s_i$ 的时刻）。

对每名选手，输出他到达楼层 $f_i$ 的最早时刻。

若电梯恰好在时刻 $t_i$ 停在楼层 $s_i$，则第 $i$ 名选手可以立刻进入电梯。若选手出发的楼层 $s_i$ 恰好就是他想去的楼层（$s_i = f_i$），则他到达楼层 $f_i$ 的时刻视为 $t_i$。

输入格式

第一行包含两个用空格隔开的整数 $n$ 和 $m$（$1 \le n \le 10^5$，$2 \le m \le 10^8$）。接下来 $n$ 行，每行描述一名选手：三个用空格隔开的整数 $s_i$、$f_i$、$t_i$（$1 \le s_i, f_i \le m$，$0 \le t_i \le 10^8$），含义如题面所述。

输出格式

输出 $n$ 行，每行一个整数——对应选手到达目标楼层的时刻。

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

9
1
0
7
10
7
5

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

12
10
10
8
7

说明/提示

看第一组样例。第一名选手在时刻 $t=3$ 位于楼层 $s=2$。要去楼层 $f=4$，他得等到时刻 7——那是电梯第二次向上经过的时候。然后他上电梯，向上升两层，于时刻 9 到达楼层 $f$。第二名选手在时刻 $t=0$ 位于楼层 $s=1$，立刻进入电梯，于时刻 1 到达楼层 $f=2$。第三名选手不用等电梯，因为他要去的楼层就是出发楼层。