Iceberg Orders#7569

Iceberg Orders

1 second

128 megabytes

Hard

You are working for Metagonia stock exchange. Recently traders in Metagonia had heard about Iceberg orders traded on London stock exchange and asked your employer to add such functionality as well. A stock exchange is an engine that receives orders and generates trades.

An iceberg order is a quintuple of integers $(I D, T, P, V, T V)$ (ID, T, P, V, TV). Each order has an identifier $I D$ (unique among all orders), type $T$ (which is equal to either $B U Y = 1$ BUY = 1 or $S E LL = 2$ SELL = 2), price $P$ , total remaining volume $V$ and tip volume $T V$ . For each order, exchange additionally keeps track of its current volume $C V$ and priority $P R$ . There is also a global priority counter of the exchange $GP$ . An order book of the exchange is a set of orders.

Trades that are generated by the exchange are quadruples of integers $(B U Y - I D, S E LL - I D, P, V)$ (BUY\text{-}ID, SELL\text{-}ID, P, V). Each trade has $B U Y - I D$ BUY\text{-}ID and $S E LL - I D$ SELL\text{-}ID - identifiers of matching BUY and SELL orders, trade price $P$ , and trade volume $V$ .

When an order is received by the exchange it is matched against orders currently on the order book. This is done as follows. Suppose an order $a$ is received with $T_{a} = S E LL$ T_a = SELL. Among all orders currently on the order book we look for an order $b$ such that $T_{b} = B U Y$ T_b = BUY and $P_{b} \geq P_{a}$ P_b \geq P_a. We select such an order $b$ with the largest price, and if there are several - one with the smallest priority. If there is such an order $b$ , then $a$ trade $t$ is generated with $B U Y - I D_{t} = I D_{b}$ BUY\text{-}ID_t = ID_b and $S E LL - I D_{t} = I D_{a}$ SELL\text{-}ID_t = ID_a at trade price $P_{t} = P_{b}$ P_t = P_b with trade volume $V_{t} = min (V_{a}, C V_{b})$ V_t = \min(V_a,\,CV_b). $V_{a}$ V_a, $V_{b}$ V_b, and $C V_{b}$ CV_b are all decreased by trade volume. If $V_{b} = 0$ V_b = 0 after this, then the order $b$ is removed from the order book. If $C V_{b} = 0$ CV_b = 0 (but $V_{b} > 0$ V_b > 0) then we set current volume of order $b$ to $C V_{b} = min (V_{b}, T V_{b})$ CV_b = \min(V_b,\,TV_b), set $P R_{b} = GP$ PR_b = GP, and increment $GP$ . We continue these operations of selecting $b$ and generating trades until either $V_{a} = 0$ V_a = 0 or there are no more orders $b$ on the order book which satisfy the condition. In the latter case, we add order $a$ to the order book with $C V_{a} = min (V_{a}, T V_{a})$ CV_a = \min(V_a,\,TV_a) and $P R_{a} = GP$ PR_a = GP, and then increment $GP$ . When the process of matching the order $a$ is finished with several trades between the same pair of orders $a$ and $b$ (and there can be lots of them!), they are all united into a single trade with the volume equal to the sum of individual trade volumes.

If $T_{a} = B U Y$ T_a = BUY we are looking for an order $b$ with $T_{b} = S E LL$ T_b = SELL and $P_{b} \leq P_{a}$ P_b \leq P_a and select such an order $b$ with the smallest price and the smallest priority among those. The rest of the matching process is as described above, with trades having $B U Y - I D_{t} = I D_{a}$ BUY\text{-}ID_t = ID_a, $S E LL - I D_{t} = I D_{b}$ SELL\text{-}ID_t = ID_b, $P_{t} = P_{b}$ P_t = P_b, and $V_{t} = min (V_{a}, C V_{b})$ V_t = \min(V_a,\,CV_b).

Initially the order book is empty. You are presented with several orders that are received by the exchange one by one. You need to print generated trades and the order book state after all orders are processed.

Hint: The priority and $GP$ are introduced in the problem statement only for the purpose of a formal description of the algorithm. The actual implementation does not have to keep track of priority. Typically, an exchange simply keeps a priority-ordered list of orders of each type at each price in its order book.

Input

The first line contains the number of orders $n$ ( $1 \leq n \leq 50000$ 1 \leq n \leq 50000). Each of the following $n$ lines represent an order. Each order is given by a space-separated quintuple $I D T P V T V$ ID\,T\,P\,V\,TV, where $1 \leq I D \leq 1000000$ 1 \leq ID \leq 1000000, $T = 1$ T = 1 for BUY and $T = 2$ T = 2 for SELL, $1 \leq P \leq 100000$ 1 \leq P \leq 100000 and $1 \leq T V \leq V \leq 1 0^{9}$ 1 \leq TV \leq V \leq 10^9.

Output

For each order print all trades generated by processing this order, in ascending order of pairs $(B U Y - I D, S E LL - I D)$ (BUY\text{-}ID, SELL\text{-}ID), each trade on its own line. Each trade shall be printed as a space-separated quadruple of integers $B U Y - I D S E LL - I D P V$ BUY\text{-}ID\,SELL\text{-}ID\,P\,V. It is guaranteed that the total number of trades would not exceed $100000$ . Print a blank line after all trades, followed by the order book. Each order that is still on the book shall be printed as a space-separated sextuple $I D T P V T V C V$ ID\,T\,P\,V\,TV\,CV, sorted first by $P$ and then by $P R$ .

Examples

Example 1

Note

In the sample input the first four orders have $T = B U Y$ T = BUY. Assuming that at the beginning $GP$ at the exchange was equal to $1$ , after receiving these orders the order book looks in the following way when ordered according to the matching rules from the problem statement for $T_{b} = B U Y$ T_b = BUY orders (first by the largest price, then by the smallest priority):

The fifth order (with $I D_{a} = 4321$ ID_a = 4321) has $T_{a} = S E LL$ T_a = SELL, $P_{a} = 99$ P_a = 99 and $V_{a} = 125$ V_a = 125 and is eligible for match with all of the above four orders given in the above table. First, it matches twice with the order $1111$ with the highest price of $101$ for a total trade volume of $30$ , removes it from the order book, bumps $GP$ to $6$ in the process, and decreases $V_{a}$ V_a to $95$ . Then, there are three other orders at price $100$ . One matching pass through them produces three trades for a total volume of $85$ (volume $20$ with order $42$ , volume $50$ with order $239$ , removes it from the book, volume $15$ with order $1234$ ), bumps $GP$ to $8$ , and decreases $V_{a}$ V_a to $10$ . The remaining orders in the book are shown below:

One last match with the order $42$ produces a trade with a volume of $10$ (for a total volume of $30$ for matches with order $42$ ) and the order $4321$ is done ( $V_{a} = 0$ V_a = 0). Four corresponding total trades for order $4321$ are printed in the sample output. The remaining order book is:

The sixth BUY order (with $I D = 5678$ ID = 5678) is added to the order book ( $GP$ becomes $9$ ):

The last, seventh order (with $I D = 8765$ ID = 8765), can be matched only with the order $5678$ due to price condition, generates a trade with volume of $30$ , order $5678$ is removed from the order book, while order $8765$ is added. Now the order book has both BUY and SELL orders: