Berland.Taxi is a new taxi company with k cars which started operating in the capital of Berland just recently. The capital has n houses on a straight line numbered from 1 (leftmost) to n (rightmost), and the distance between any two neighboring houses is the same. You have to help the company schedule all the taxi rides which come throughout the day according to the following rules: All cars are available for picking up passengers. Initially the j -th car is located next to the house with the number x j at time 0 . All cars have the same speed. It takes exactly 1 minute for any car to travel between neighboring houses i and i + 1 . The i -th request for taxi ride comes at the time t i , asking for a passenger to be picked up at the house a i and dropped off at the house b i . All requests for taxi rides are given in the increasing order of t i . All t i are distinct. When a request for taxi ride is received at time t i , Berland.Taxi operator assigns a car to it as follows: Out of cars which are currently available, operator assigns the car which is the closest to the pick up spot a i . Needless to say, if a car is already on a ride with a passenger, it won't be available for any rides until that passenger is dropped off at the corresponding destination. If there are several such cars, operator will pick one of them which has been waiting the most since it became available. If there are several such cars, operator will pick one of them which has the lowest number . After a car gets assigned to the taxi ride request: The driver immediately starts driving from current position to the house a i . Once the car reaches house a i , the passenger is immediately picked up and the driver starts driving to house b i . Once house b i is reached, the passenger gets dropped off and the car becomes available for new rides staying next to the house b i . It is allowed for multiple cars to be located next to the same house at the same point in time, while waiting for rid