Stock Exchange Order Matching Engine

Implement a simplified stock-exchange order matching engine. The system receives N limit orders in arrival order. Each order has the format: side order_id price quantity Where: side is B (buy) or S (sell); order_id is a unique integer; price and quantity are positive integers; all orders are limit orders; cancellations and amendments are not supported. The order book must enforce price-time priority: On the buy side, higher prices have priority; orders at the same price are prioritized by earlier arrival time. On the sell side, lower prices have priority; orders at the same price are prioritized by earlier arrival time. For every incoming order: An incoming buy matches the best resting sell while its price is at least the best ask. An incoming sell matches the best resting buy while its price is at most the best bid. The execution quantity is the minimum remaining quantity of the two orders. Partial fills are allowed. The execution price is the price of the existing resting order. Immediately print one record per execution: TRADE buy_order_id sell_order_id trade_price trade_quantity Any unfilled portion of the incoming order becomes a resting order. After all orders are processed, print: BOOK Then print all remaining orders: Buy orders first, sorted by descending price and then ascending arrival time. Sell orders next, sorted by ascending price and then ascending arrival time. Use one of the following formats per order: B order_id price remaining_quantity or S order_id price remaining_quantity Example Input: 4 B 1 100 10 S 2 105 4 S 3 99 6 S 4 100 8 Output: TRADE 1 3 100 6 TRADE 1 4 100 4 BOOK S 4 100 4 S 2 105 4 Constraints 1 <= N <= 200,000 1 <= order_id <= 10^9, and all IDs are unique 1 <= price, quantity <= 10^9 Design an efficient solution for a large order stream. Example Input 4 B 1 100 10 S 2 105 4 S 3 99 6 S 4 100 8 Output TRADE 1 3 100 6 TRADE 1 4 100 4 BOOK S 4 100 4 S 2 105 4