Marketplace Data Store: Order Matching and End-of-Day Reconciliation

You are building the core of a marketplace where sellers list individual units of items for sale and buyers submit buy orders.

Each listing represents one unit for sale and has the fields:

• item_name (string) — the name of the item,
• seller (string) — the seller's name,
• price (integer) — the asking price for this unit,
• buyer (optional string) — null while the unit is unsold; set to the buyer's name once the unit is sold.

All listings live in a DataStore that supports two operations:

• update(listing) — insert a new listing or modify an existing one (for example, setting buyer when a unit is sold),
• getAll() — return all current listings.

Implement the DataStore and the two tasks below.

Part 1 — Fill buy orders

You are given the current contents of the DataStore and a collection of buy orders, at most one per item name: a map item_name -> (buyer_name, limit_price), meaning the named buyer wants to purchase exactly one unit of item_name and is willing to pay at most limit_price.

Process each buy order as follows:

• Consider the unsold listings (buyer == null) whose item_name matches the order.
• The order fills against the lowest-priced such listing whose price <= limit_price. If several qualifying listings tie at that lowest price, fill the one that was inserted into the DataStore earliest.
• The final transaction price is that listing's price (not the buyer's limit price). Mark the listing as sold by setting its buyer to buyer_name via update.
• If no unsold listing qualifies, the order does not fill and the DataStore is unchanged for that order.

Return a map item_name -> final_price containing one entry for every order that filled. Orders that did not fill do not appear in the result.

Part 2 — End-of-day reconciliation

At the end of the trading day you receive the full day's transaction log. Each log record has:

• buyer_name (string),
• item_name (string),
• price (integer) — for OK and PAYMENT_FAILED records, the price the buyer transacted at; for OUT_OF_STOCK records, the maximum price the buyer was willing to pay,
• timestamp (integer) — all timestamps are distinct,
• status — one of:
• OK: the buyer bought a unit of item_name at price and the payment settled,
• PAYMENT_FAILED: the buyer bought a unit of item_name at price, but the payment later bounced (e.g., a credit-card problem), so the purchase is voided,
• OUT_OF_STOCK: the buyer wanted one unit of item_name for at most price, but no unit was available at that moment, so nothing was bought.

Reconcile the day by scanning the records in increasing timestamp order while maintaining a pool of re-opened units (units returned to the market during this scan). Apply these rules:

1. PAYMENT_FAILED at price p: the unit the buyer had bought re-opens for sale — add the unit (item_name, p) to the pool. The buyer was never successfully charged, so they receive no billing adjustment.
2. OK at price p: if the pool contains at least one re-opened unit of the same item_name with price strictly less than p, the buyer should have gotten that cheaper unit instead. Reassign the buyer to the cheapest such pool unit (earliest-added wins ties), whose price is q: record a refund of p - q for this buyer, remove that unit from the pool, and add the buyer's original unit (item_name, p) to the pool (it re-opens for sale). If the pool has no unit of this item cheaper than p, nothing happens.
3. OUT_OF_STOCK with limit price b: if the pool contains at least one re-opened unit of the same item_name with price q <= b, the buyer's unfilled demand can now be satisfied. Assign the buyer the cheapest such pool unit (earliest-added wins ties): record a charge of q for this buyer and remove the unit from the pool. If no pool unit qualifies, nothing happens.

Note that a re-opened unit can only affect records that come after it in timestamp order: an OUT_OF_STOCK order whose timestamp precedes every relevant PAYMENT_FAILED record is never charged.

Return the list of billing adjustments as (buyer_name, adjustment_type, amount) triples, where adjustment_type is "refund" or "charge", in the order the adjustments are produced by the scan. A buyer may appear more than once if several of their records trigger adjustments.

Example — Scenario A

Transaction log (already shown in timestamp order):

• Alice's payment failed, so the unit (itemA, 100) re-opens.
• Bob successfully paid 110, but a unit of itemA at 100 (< 110) is in the pool: Bob is reassigned to it and refunded 110 - 100 = 10; his original unit (itemA, 110) re-opens.
• Cathy paid 105; the only pool unit for itemA costs 110, which is not cheaper than 105, so nothing happens.

Output: [("Bob", "refund", 10)]

Example — Scenario B

• Alice's payment failed, so the unit (itemA, 100) re-opens.
• David had wanted itemA for at most 110 but found no stock; the pool now holds (itemA, 100) with 100 <= 110, so David gets that unit and is charged 100.

Output: [("David", "charge", 100)]

If instead David's OUT_OF_STOCK record had a timestamp before Alice's failure, no unit would be in the pool at his position in the scan, and David would not be charged.

Constraints

• 1 <= number of listings, buy orders, log records <= 10^5
• 1 <= price, limit_price <= 10^9
• Timestamps are distinct integers; the log is not guaranteed to arrive sorted.
• Names (item_name, seller, buyer_name) are non-empty case-sensitive strings.
• Each buyer appears at most once per timestamp; a single buyer may have multiple records across the day.
• Target overall time complexity: O((n + m) log (n + m)) where n is the number of listings/orders and m is the number of log records.