Iceberg Orders

Вы работаете на бирже Метагония. Недавно торговцы в Метагонии услышали о заявках айсберга, торгуемых на Лондонской фондовой бирже, и попросили вашего работодателя добавить такую функциональность. Фондовая биржа - это финансовый институт, который получает заказы и генерирует сделки.

Заявка айсберга - это пятека целых чисел (ID, T, P, V, TV). Каждая заявка имеет идентификатор ID (уникальный для всех заявок), тип T (равный либо BUY = 1 или SELL = 2), цену P, общий оставшийся объем V и видимый объем TV . Для каждой заявки дополнительно отслеживается ее текущий объем CV и приоритет PR. Существует также глобальный счетчик приоритетов обмена GP. Заявка включается в набор заявок биржи.

Торги, которые генерируются на бирже, представляют собой четыре целых числа (BUY-ID, SELL-ID, P, V). Каждая сделка содержит BUY-ID и SELL-ID - идентификаторы соответствия ПОКУПАТЬ и ПРОДАВАТЬ заказы, торговую цену P и объем торгов V.

Когда заявка выставляется на торги, она сопоставляется с заявками, находящимися в настоящее время в реестре заявок. Это происходит следующим образом. Пусть получен заказ a, у которого T[a] = SELL. Среди всех заявок, выставленных на торги, мы ищем заявку b такую что T[b] = BUY и P[b] ≥ P[a]. Мы выбираем такую заявку b, которая имеет наибольшую цену, а если таких несколько - то имеющую наименьший приоритет. Если такая заявка b существует, то a генерирует торговую сделку t у которой BUY-ID[t] = ID[b] и SELL-ID[t] = ID[a] по цене P[t] = P[b] объемом V[t] = min(V[a],CV[b]). Значения V[a], V[b] и CV[b] уменьшаются на объем сделки. Если после этого V[b] = 0, то заявка b удаляется из реестра заявок. Если CV[b] = 0 (но V[b] > 0), то устанавливаем текущий объем заявки b равным CV[b] = min(V[b], TV[b]), устанавливаем PR[b] = GP, и увеличиваем GP. Продолжаем операции выбора b и генерирования торгов пока не станет либо V[a] = 0, либо не станет больше таких заявок b в реестре, удовлетворяющих условию возможности торгов. In the latter case, we add order a to the order book with CV[a] = min(V[a], TV[a]) and 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] = BUY we are looking for an order b with T[b] = SELL and P[b] ≤ 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 BUY-ID[t] = ID[a], SELL-ID[t] = ID[b], P[t] = P[b], and 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.

Входные данные

Первая строка содержит количество заявок n (1 ≤ n ≤ 50000). Каждая из следующих n строк представляет заявку. Каждая заявка задается пятеркой ID T P V TV, где 1 ≤ ID ≤ 1000000, T = 1 для BUY и T = 2 для SELL, 1 ≤ P ≤ 100000 и 1 ≤ TV ≤ V ≤ 10^9.

Выходные данные

For each order print all trades generated by processing this order, in ascending order of pairs (BUY-ID, SELL-ID), each trade on its own line. Each trade shall be printed as a space-separated quadruple of integers BUY-ID SELL-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 ID T P V TV CV, sorted first by P and then by PR.

Примеры

Примечание

В примере первые четыре заявки имеют T = BUY. Предполагая что в начале торгов GP равнялось 1, после получения этих заявок реестр выглядит следующим образом, упорядоченный по правилам соответствия из условия задачи для T[b] = BUY (сначала по убыванию цены, затем по возрастанию приоритета):

Пятая заявка (ID[a] = 4321) имеет T[a] = SELL, P[a] = 99 и 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] 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] 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). Four corresponding total trades for order 4321 are printed in the sample output. The remaining order book is:

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

The last, seventh order (with 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: