|Codeforces Round #159 (Div. 2)|
The m-floor (m > 1) office of international corporation CodeForces has the advanced elevator control system established. It works as follows.
All office floors are sequentially numbered with integers from 1 to m. At time t = 0, the elevator is on the first floor, the elevator is empty and nobody is waiting for the elevator on other floors. Next, at times ti (ti > 0) people come to the elevator. For simplicity, we assume that one person uses the elevator only once during the reported interval. For every person we know three parameters: the time at which the person comes to the elevator, the floor on which the person is initially, and the floor to which he wants to go.
The movement of the elevator between the floors is as follows. At time t (t ≥ 0, t is an integer) the elevator is always at some floor. First the elevator releases all people who are in the elevator and want to get to the current floor. Then it lets in all the people waiting for the elevator on this floor. If a person comes to the elevator exactly at time t, then he has enough time to get into it. We can assume that all of these actions (going in or out from the elevator) are made instantly. After that the elevator decides, which way to move and at time (t + 1) the elevator gets to the selected floor.
The elevator selects the direction of moving by the following algorithm.
Your task is to simulate the work of the elevator and for each person to tell the time when the elevator will get to the floor this person needs. Please note that the elevator is large enough to accommodate all the people at once.
The first line contains two space-separated integers: n, m (1 ≤ n ≤ 105, 2 ≤ m ≤ 105) — the number of people and floors in the building, correspondingly.
Next n lines each contain three space-separated integers: ti, si, fi (1 ≤ ti ≤ 109, 1 ≤ si, fi ≤ m, si ≠ fi) — the time when the i-th person begins waiting for the elevator, the floor number, where the i-th person was initially located, and the number of the floor, where he wants to go.
Print n lines. In the i-th line print a single number — the moment of time, when the i-th person gets to the floor he needs. The people are numbered in the order, in which they are given in the input.
Please don't use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
1 2 7
3 6 5
3 4 8
1 2 5
7 4 5
In the first sample the elevator worked as follows: