Simulating Iceberg Orders

You are working for the Metagonia stock exchange. Traders have requested iceberg order functionality similar to that used on the London stock exchange. An iceberg order is represented by a quintuple of integers \( (ID, T, P, V, TV) \), where:

• ID is a unique identifier.
• T is the type and equals \(1\) (BUY) or \(2\) (SELL).
• P is the price.
• V is the total remaining volume.
• TV is the tip volume.

The exchange also maintains a current volume \(CV\) for each order. When an order is inserted into the order book, its \(CV\) is set to \(min(V, TV)\) (written in \(\LaTeX\) as \(CV = \min(V, TV)\)).

Orders are processed one by one. When a new order \(a\) is received:

• If \(T_a = 2\) (SELL), the exchange searches for a BUY order \(b\) in the book such that \(P_b \ge P_a\). Among those, the order with the largest price is chosen, and if there are several, the one with the earliest arrival (lowest priority). A trade is then generated with:

\(BUY\_ID = ID_b, \quad SELL\_ID = ID_a, \quad P_t = P_b, \quad V_t = \min(V_a, CV_b)\).

• If \(T_a = 1\) (BUY), the exchange searches for a SELL order \(b\) such that \(P_b \le P_a\); the order with the smallest price (and earliest arrival on ties) is selected, and the trade is generated with \(BUY\_ID = ID_a, \; SELL\_ID = ID_b, \; P_t = P_b, \; V_t = \min(V_a, CV_b)\).

After a trade:

• The volumes \(V_a, V_b\) and the current volume \(CV_b\) decrease by \(V_t\).
• If an order’s \(V\) becomes zero it is removed from the order book.
• If \(CV_b\) becomes zero but \(V_b > 0\), then the order's \(CV_b\) is replenished by \(\min(V_b, TV_b)\).

Multiple trades between the same pair of orders that occur in the processing of a single incoming order must be combined into one trade record with volume equal to the sum of individual trades.

If after matching there is remaining volume in order \(a\), it is added to the order book with \(CV_a = \min(V_a, TV_a)\).

At the end, output the list of generated trades (each as a quadruple of integers) followed by the final state of the order book (each order printed as ID T P V CV TV on a separate line).

inputFormat

The first line contains an integer \(N\) representing the number of orders. Each of the following \(N\) lines contains 5 space-separated integers: ID T P V TV, where T is 1 for BUY and 2 for SELL.

outputFormat

First, output all trades generated during the processing of orders. Each trade is printed on a separate line as 4 space‐separated integers: BUY_ID SELL_ID P V. If several trades occur between the same pair during processing of an order, they are merged into one trade (the volume is the sum of the individual trades).

Then, print a line containing Order Book: (without quotes). After that, for each order remaining in the order book, output a line with 6 space‐separated integers: ID T P V CV TV.

sample

3
1 1 100 10 5
2 2 90 5 3
3 2 95 10 4

1 2 100 5
1 3 100 5
Order Book:
3 2 95 5 4 4

</p>