Top-of-Book Ticker

You are building the ticker component of a market data feed: after every order book event, it must publish the current top of book (best bid and best ask).

You receive a list of events, in sequence. Each event is one of:

• ("add", order_id, side, price, qty): a new limit order enters the book. side is "B" for a bid (buy) or "S" for an ask (sell). Prices are integer ticks. order_id values of add events are unique.
• ("cancel", order_id): the order leaves the book. A cancel may reference an id that was never added or was already cancelled; treat that as a no-op.

Implement top_of_book(events) returning a list with one entry per event: the tuple (best_bid, best_ask) immediately after applying that event. The best bid is the highest live bid price, the best ask is the lowest live ask price. Use None for a side with no live orders. Order quantity never changes and does not affect the top of book in this problem.

Example

events = [
    ("add", 1, "B", 100, 5),
    ("add", 2, "S", 102, 3),
    ("add", 3, "B", 101, 2),
    ("cancel", 3),
]
top_of_book(events)
# [(100, None), (100, 102), (101, 102), (100, 102)]

Constraints

• Up to \(10^5\) events.
• Prices are positive integers; multiple live orders may share a price.
• Your solution must handle the event volume comfortably: recomputing the best price by scanning every live order on every event will not finish in time.