Обмін#6295
Ви берете участь у великому проєкті з автоматизації операцій для Північно-Східної Біржі Ресурсів та Товарів (NEERC). На цій біржі різні ресурси та товари торгуються через публічний аукціон. Кожен ресурс або товар торгується незалежно від інших, і ваше завдання — написати основний механізм для цієї біржі — її книгу заявок. Існує окремий екземпляр книги заявок для кожного торгованого ресурсу або товару, і це не ваша проблема отримати правильні заявки в книги заявок. Екземпляр книги заявок, який ви будете писати, отримуватиме відповідні заявки з решти системи біржі.
Книга заявок отримує потік повідомлень. Повідомлення — це заявки та запити на скасування раніше виданих заявок. Заявки, які не були скасовані, називаються активними. Існують заявки на купівлю та заявки на продаж. Кожна заявка на купівлю або продаж має позитивний розмір і позитивну ціну. Книга заявок підтримує список активних заявок і генерує котирування та угоди. Активна заявка на купівлю за найвищою ціною є найкращою заявкою на купівлю, і її ціна називається ціною пропозиції (bid price). Активна заявка на продаж за найнижчою ціною є найкращою заявкою на продаж, і її ціна називається ціною запиту (ask price). Ціна запиту завжди нижча за ціну пропозиції, тобто покупці готові платити менше, ніж продавці хочуть отримати в обмін.
Поточне котирування з книги заявок містить поточний розмір пропозиції, ціну пропозиції, розмір запиту та ціну запиту. Тут розміри пропозиції та запиту є сумами розмірів усіх активних заявок з поточною ціною пропозиції та поточною ціною запиту відповідно.
Угода записує інформацію про транзакцію між покупцем і продавцем. Кожна угода має розмір і ціну.
Якщо заявка на купівлю надходить до книги заявок за ціною, що дорівнює або перевищує поточну ціну запиту, то відповідні заявки зіставляються і відбувається угода — покупець і продавець досягли згоди щодо ціни. І навпаки, якщо заявка на продаж надходить до книги заявок за ціною, що дорівнює або менша за поточну ціну пропозиції, то також відбувається угода. Для цілей зіставлення заявок книга заявок працює як черга FIFO для заявок з однаковою ціною (читайте далі для деталей).
Коли заявка на купівлю надходить до книги заявок за ціною, що дорівнює або перевищує поточну ціну запиту, вона не відразу заноситься в книгу заявок. Спочатку генерується кілька угод, можливо, зменшуючи розмір вхідної заявки. Угода генерується між вхідною заявкою на купівлю та найкращою заявкою на продаж. Якщо є кілька найкращих заявок (за ціною запиту), то обирається заявка, яка першою надійшла в книгу заявок. Угода генерується за поточною ціною запиту з розміром угоди, що дорівнює меншому з розмірів двох зіставлених заявок. Розміри обох зіставлених заявок зменшуються на розмір угоди. Якщо це зменшує розмір заявки на продаж до нуля, то вона стає неактивною і видаляється з книги заявок. Якщо розмір вхідної заявки на купівлю стає нульовим, то процес завершено — вхідна заявка стає неактивною. Якщо розмір вхідної заявки на купівлю все ще позитивний і є інша заявка на продаж для зіставлення, то процес продовжується, генеруючи подальші угоди за новою ціною запиту (ціна запиту може збільшуватися, оскільки заявки на продаж торгуються і стають неактивними). Якщо немає заявки на продаж для зіставлення (поточна ціна запиту стала більшою за ціну вхідної заявки на купівлю), то вхідна заявка на купівлю додається до книги заявок з її залишковим розміром.
Для вхідної заявки на продаж все працює аналогічно — вона зіставляється з заявками на купівлю з книги заявок, і угоди генеруються за ціною пропозиції.
На вхідний запит на скасування відповідна заявка просто видаляється з книги заявок і стає неактивною. Зверніть увагу, що на момент запиту на скасування кількість відповідної заявки могла вже частково зменшитися або заявка могла стати неактивною. Запити на скасування неактивної заявки нічого не змінюють у книзі заявок.
На кожне вхідне повідомлення книга заявок повинна генерувати всі угоди, які воно спричиняє, і поточне котирування (розмір пропозиції, ціна пропозиції, розмір запиту, ціна запиту) після обробки відповідного повідомлення, навіть якщо нічого не змінилося в книзі заявок в результаті цього повідомлення. Таким чином, кількість котирувань, які генерує книга заявок, завжди дорівнює кількості вхідних повідомлень.
Перша строка вхідних даних містить одне ціле число (1 \le n \le 10000) — кількість вхідних повідомлень, які книга заявок повинна обробити. Наступні рядків містять повідомлення. Кожен рядок починається зі слова, що описує тип повідомлення — BUY, SELL або CANCEL, після якого йдуть параметри повідомлення.
BUY та SELL позначають заявку на купівлю або продаж відповідно, і супроводжуються двома цілими числами та (1 \le q \le 99999, 1 \le p \le 99999) — розмір заявки та ціна. CANCEL позначає запит на скасування раніше виданої заявки. Він супроводжується одним цілим числом , яке є номером повідомлення з деякою попередньою заявкою на купівлю або продаж (повідомлення нумеруються від до ).
Виведіть потік котирувань та угод, які генерують вхідні повідомлення. Для кожної угоди виведіть TRADE, після якого йдуть розмір угоди та ціна. Для кожного котирування виведіть QUOTE, після якого йдуть розмір пропозиції, ціна пропозиції, мінус ("-"), розмір запиту, ціна запиту (усі розділені пробілами).
Існує особливий випадок, коли в книзі заявок немає активних заявок на купівлю або продаж (пропозиція та/або запит не визначені). Цей випадок розглядається наступним чином. Якщо немає активної заявки на купівлю, то вважається, що розмір пропозиції дорівнює нулю, а ціна пропозиції дорівнює нулю. Якщо немає активної заявки на продаж, то вважається, що розмір запиту дорівнює нулю, а ціна запиту дорівнює . Зверніть увагу, що нуль не є легальною ціною, але є легальною ціною. Одержувач повідомлень про котирування розрізняє фактичну ціну запиту від особливого випадку відсутності заявок на продаж, дивлячись на її розмір запиту.
Дивіться приклад для подальшого роз'яснення.
Приклад 1