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 t i ( t i > 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. If the elevator is empty and at the current time no one is waiting for the elevator on any floor, then the elevator remains at the current floor. Otherwise, let's assume that the elevator is on the floor number x (1 ≤ x ≤ m ) . Then elevator calculates the directions' "priorities" p up and p down : p up is the sum of the number of people waiting for the elevator on the floors with numbers greater than x , and the number of people in the elevator, who want to get to the floors with the numbers greater than x ; p down is the sum of the number of people waiting for the elevator on the floors with numbers less than x