The Office Elevator

One elevator serves a tall building, and you will simulate it one second (one tick) at a time.

Write elevator(passengers, capacity). Each passenger is a tuple (arrive, start, dest): from tick arrive they wait on floor start, wanting to go to floor dest (never the same as start). They want to go up if dest is above start and down otherwise. At most capacity people fit in the elevator at once.

The elevator starts on floor 0, empty and idle, at tick 0. At every tick these steps happen in order:

1. Arrivals. Every passenger whose arrive is this tick starts waiting. 2. Exits. Riders whose dest is this floor get out. Their trip ends at this tick. 3. Direction. - Going up: keep going up if a rider's dest is above, someone is waiting on a floor above, or someone waiting on this floor wants to go up. Otherwise turn to go down if anyone is still waiting, or become idle if no one is. - Going down: the same, with up and down swapped. - Idle: if someone is waiting on this floor, take the direction of the one who has waited longest. Otherwise, if anyone is waiting, head toward the nearest floor where someone waits (if two are equally near, go down). If no one waits, stay idle. 4. Boarding. If the elevator now has a direction, the people waiting on this floor who want to go that way get in, longest-waiting first, while there is room. 5. Moving. Unless it is idle, the elevator moves one floor in its direction, arriving there at the next tick.

"Waited longest" means the earliest arrive, and on a tie the passenger who comes first in passengers. Return a list with the tick at which each passenger reached their floor, in the same order as passengers.

Examples

elevator([(0, 0, 3)], 1)                          # returns [3]
elevator([(0, 2, 0)], 4)                          # returns [4]
elevator([(0, 0, 5), (1, 3, 1), (2, 4, 6)], 4)    # returns [5, 11, 6]

In the last example the elevator carries the first passenger up. It passes floor 3, where the second passenger waits, but she wants to go down, so she has to wait. It picks up the third passenger on floor 4, drops the first at floor 5 (tick 5) and the third at floor 6 (tick 6), turns around, collects the second passenger on floor 3 at tick 9 and reaches floor 1 at tick 11.

Constraints

• 1 <= len(passengers) <= 200 and 1 <= capacity <= 20
• 0 <= arrive <= 1,000 and 0 <= start, dest <= 100