Parking Lot With a Waiting Line

A small parking lot has spaces parking spaces and, at the gate, room for line_size cars to wait in a line. The barrier keeps a log of events, each a string 'in PLATE' (a car arrives) or 'out PLATE' (a car wants to leave). Handle the events in order:

• A car arrives. If a space is free, it parks. Otherwise, if fewer than line_size cars are waiting, it joins the end of the line. Otherwise it is turned away and drives off.
• A parked car leaves. Its space becomes free, and the first car in the line, if there is one, moves into it.
• A waiting car leaves. It gives up and leaves the line, and the cars behind it move up.
• A car that is neither parked nor waiting leaves (it was turned away earlier). Nothing happens.

Write turned_away(spaces, line_size, events) that returns the list of plates that were turned away, in the order it happened. A car that is turned away twice appears twice.

Examples

events = ['in A1', 'in B2', 'in C3', 'in D4', 'out A1', 'in E5']
turned_away(2, 1, events)   # returns ['D4']
turned_away(2, 0, events)   # returns ['C3', 'D4']

With 2 spaces and room for 1 waiting car, A1 and B2 park, C3 waits at the gate and D4 is turned away. When A1 leaves, C3 takes its space, so E5 finds room in the line. With no room to wait, C3 and D4 are both turned away, and E5 parks in the space A1 left.

Constraints

• 1 <= spaces <= 1,000 and 0 <= line_size <= 1,000
• events has 0 to 30,000 items.
• A car never arrives while it is parked or waiting in the line.