Implement a Simplified Stock Exchange Order Matching Engine

Problem: Implement a Simplified Stock Exchange Order Matching Engine Build a simplified order matching system that processes buy and sell orders and maintains an order book. Matching must follow price-time priority. Matching Rules Buy book (bids): higher price first; for the same price, earlier arrival first. Sell book (asks): lower price first; for the same price, earlier arrival first. A match happens when best_bid_price >= best_ask_price: Use the ask price as the trade price (unless specified otherwise). Trade quantity is min(buy_remaining_qty, sell_remaining_qty). If an order is partially filled, the remaining quantity stays in the book. After inserting a new order, keep matching until no further match is possible. Input (stdin) First line: integer N (#orders) Next N lines: side price quantity timestamp side is B (buy) or S (sell) price, quantity are positive integers timestamp is an integer used for time priority (smaller means earlier) Output (stdout) Print one line per trade: trade_price trade_quantity buy_timestamp sell_timestamp Constraints 1 <= N <= 2e5 1 <= price, quantity <= 1e9 timestamp is not guaranteed to be strictly increasing Target complexity: about O(N log N) Examples (See the 5 test cases in the Chinese statement.) Example Input 4 B 100 10 1 S 105 5 2 S 99 7 3 B 101 3 4 Output 99 7 1 3