Elevator Selection Problem

You are given a building with N floors, and M elevators. For each elevator, you are provided its current floor, the current motion status (which can be either "up", "down", or "still"), and a sequence of floors currently in its queue (which can be empty). Additionally, a request is made from a starting floor to a destination floor.

Your task is to choose the elevator that should respond to the request such that the total travel time to reach the starting floor is minimized. The travel time for an elevator is computed as follows:

• If the elevator is idle (i.e. its status is "still"), then
  $$T = |\text{current floor} - \text{start}|.$$
• If the elevator is moving in the same direction as the desired request (determined by comparing the starting and destination floors), then:
  • For an upward request (destination > start) and when the elevator is below or at the starting floor,
    $$T = \text{start} - \text{current floor}.$$
  • For a downward request (destination < start) and when the elevator is above or at the starting floor,
    $$T = \text{current floor} - \text{start}.$$
  • If these conditions are not met, the travel time is considered infinite.
• In any other scenario, the travel time is treated as infinite.

If no elevator in motion in the correct direction is available, select the elevator (among all) with the smallest idle travel time.

Return the index (0-indexed) of the chosen elevator.

inputFormat

The input is read from standard input (stdin) in the following format:

N M
C₀ D₀ k₀ a₀₁ a₀₂ ... a₀ₖ₀
C₁ D₁ k₁ a₁₁ a₁₂ ... a₁ₖ₁
... 
Cₘ₋₁ Dₘ₋₁ kₘ₋₁ a₍ₘ₋₁₎₁ a₍ₘ₋₁₎₂ ... a₍ₘ₋₁₎ₖₘ₋₁
start destination

Here,

• N is the total number of floors.
• M is the number of elevators.
• Each of the next M lines describes an elevator:
• C is the current floor of the elevator.
• D is a string indicating the elevator's current direction ("up", "down", or "still").
• k is the number of floors in its queue.
• The following k integers are the floors in its queue (if any).
• The final line contains two integers: the starting floor and the destination floor for the request.

outputFormat

Output a single integer to standard output (stdout), which is the 0-indexed index of the chosen elevator.

## sample

10 3
1 up 2 5 10
4 down 2 3 2
6 still 0
3 7

0