1415. Elevator

We've all ridden on an elevator and observed its behavior. In this problem, we compute the behavior of an elevator given its initial state and its departing and arriving passengers. Assume floors are numbered 1, 2, 3, …, `n` from lowest to highest (despite the anomaly that is building 8), and a single car travels up and down stopping at floors to drop off departing passengers who have reached their destination and pick up arriving passengers waiting to go to a destination in its current direction. The car executes a sweep strategy – traveling as far in its current direction as needed to visit floors ahead where departures or arrivals occur, then reversing direction and sweeping in the opposite direction. The car need not go all the way to the top or bottom floor if there are no further departures or arrivals ahead.

Input Format

The first line of input contains a positive integer `n`, which is the number of floors in the building. The second line of input gives the initial state of the car – the floor where it is stopped and the direction (`-1`=down or 1=up) it will move next. The third line of input contains zero or more floor numbers – the set of floors (excluding the initial floor) where departing passengers wish to disembark; they are the floors initially selected on the floor request panel inside the car. The remaining lines of input describe passengers who are waiting on some floor for the car; each such line contains the floor number where the passenger(s) will embark, followed by a nonempty set of floors (excluding the embarkation floor) to which they are destined.

Output Format

Given the initial state of the car, output the start state and the sequence of stops at which passenger departures and arrivals occur when the car executes the sweep strategy. At each stop the car makes (including the initial state), list departures before arrivals at the stopped floor; if there are multiple departures or arrivals going to the same floor, they should only be listed once. Note that departing passengers are willing to disembark no matter what direction the car is going, but arriving passengers are only willing to embark if the car will next move in the direction of their destination. Also note that when the direction reverses at a floor, it occurs after departing passengers disembark and before arriving passengers embark. Format the output as shown in the output sample below.

10
4 1
3 5 9
1 10
5 2 9

start        @ 4 up
departure(s) @ 5 up
arrival(s)   @ 5 up going to 9
departure(s) @ 9 up
arrival(s)   @ 5 down going to 2
departure(s) @ 3 down
departure(s) @ 2 down
arrival(s)   @ 1 up going to 10
departure(s) @ 10 up