Scenario

You’re building a simplified matching engine for a fintech brokerage app that processes hundreds of thousands of order events per minute during volatile markets. A bug in matching logic can directly impact execution quality and regulatory reporting, so correctness matters.

Problem

Implement an order book for a single asset. You will receive a sequence of operations ops, each being either:

1. ("POST", order_id, side, price, qty)
2. ("CANCEL", order_id)

Where:

• side is either "BUY" or "SELL"
• price and qty are positive integers
• order_id is unique across all POSTs

Matching Rules (Price-Time Priority)

After each POST, repeatedly match as long as the book is crossed:

• Best BUY = highest price (tie-breaker: earlier arrival)
• Best SELL = lowest price (tie-breaker: earlier arrival)
• A match occurs when best_buy.price >= best_sell.price
• Trade quantity = min(buy_remaining_qty, sell_remaining_qty)
• Trade price = the resting order’s price (the order that arrived earlier)
• If an order is fully filled, it is removed from the book; otherwise it remains with reduced quantity.

Cancellation

CANCEL makes the order immediately inactive if it is still resting with remaining quantity. Canceling an unknown or already-filled order is a no-op.

Output

Return a list of executed trades in the order they occur. Each trade is: (buy_order_id, sell_order_id, trade_price, trade_qty)

Examples

Example 1

• Input: ops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)]
• Output: [("b1","s1",100,2), ("b1","s2",100,3)]
• Explanation: Both sells cross the resting buy at 100. Trades are priced at the resting order (b1), so price is 100 for both fills.

Example 2

• Input: ops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)]
• Output: [("b2","s1",105,4), ("b1","s1",100,5)]
• Explanation: The sell matches the best buy (b2 at 105) for 4, then continues matching the next buy (b1 at 100) for 5. Each trade is priced at the resting buy.

Notes

• Use lazy deletion for canceled/filled orders in heaps.
• FIFO must be respected within the same price level.