Обмен
Вы участвуете в крупном проекте по автоматизации операций для Северо-Восточной Биржи Ресурсов и Товаров (NEERC). На этой бирже различные ресурсы и товары торгуются через публичные аукционы. Каждый ресурс или товар торгуется независимо от других, и ваша задача — разработать основной механизм для этой биржи — книгу заявок. Для каждого торгуемого ресурса или товара существует отдельный экземпляр книги заявок, и ваша задача не включает в себя обеспечение правильного попадания заявок в книги заявок. Экземпляр книги заявок, который вы будете разрабатывать, будет получать соответствующие заявки от остальной системы биржи.
Книга заявок получает поток сообщений. Сообщения могут быть заявками или запросами на отмену ранее выданных заявок. Заявки, которые не были отменены, называются активными. Существуют заявки на покупку и заявки на продажу. Каждая заявка на покупку или продажу имеет положительный размер и положительную цену. Книга заявок поддерживает список активных заявок и генерирует котировки и сделки. Активная заявка на покупку по самой высокой цене является лучшей заявкой на покупку, и ее цена называется ценой предложения. Активная заявка на продажу по самой низкой цене является лучшей заявкой на продажу, и ее цена называется ценой спроса. Цена спроса всегда ниже цены предложения, то есть покупатели готовы платить меньше, чем продавцы хотят получить взамен.
Текущая котировка из книги заявок содержит текущий размер предложения, цену предложения, размер спроса и цену спроса. Здесь размеры предложения и спроса — это суммы размеров всех активных заявок с текущей ценой предложения и текущей ценой спроса соответственно.
Сделка фиксирует информацию о транзакции между покупателем и продавцом. Каждая сделка имеет размер и цену.
Если заявка на покупку поступает в книгу заявок по цене, равной или превышающей текущую цену спроса, то соответствующие заявки сопоставляются, и происходит сделка — покупатель и продавец достигли соглашения о цене. И наоборот, если заявка на продажу поступает в книгу заявок по цене, равной или меньшей текущей цены предложения, то сделка также происходит. Для целей сопоставления заявок книга заявок работает как очередь FIFO для заявок с одинаковой ценой (читайте дальше для подробностей).
Когда заявка на покупку поступает в книгу заявок по цене, равной или превышающей текущую цену спроса, она не сразу заносится в книгу заявок. Сначала генерируется несколько сделок, возможно уменьшая размер входящей заявки. Сделка генерируется между входящей заявкой на покупку и лучшей заявкой на продажу. Если существует несколько лучших заявок (по цене спроса), то выбирается заявка, которая первой вошла в книгу заявок. Сделка генерируется по текущей цене спроса с размером сделки, равным меньшему из размеров двух сопоставленных заявок. Размеры обеих сопоставленных заявок уменьшаются на размер сделки. Если это уменьшает размер заявки на продажу до нуля, то она становится неактивной и удаляется из книги заявок. Если размер входящей заявки на покупку становится нулевым, то процесс завершен — входящая заявка становится неактивной. Если размер входящей заявки на покупку все еще положителен и есть другая заявка на продажу для сопоставления, то процесс продолжается, генерируя дальнейшие сделки по новой цене спроса (цена спроса может увеличиваться по мере того, как заявки на продажу сопоставляются и становятся неактивными). Если нет заявки на продажу для сопоставления (текущая цена спроса стала больше цены входящей заявки на покупку), то входящая заявка на покупку добавляется в книгу заявок с оставшимся размером.
Для входящей заявки на продажу все работает аналогично — она сопоставляется с заявками на покупку из книги заявок, и сделки генерируются по цене предложения.
При поступлении запроса на отмену соответствующая заявка просто удаляется из книги заявок и становится неактивной. Обратите внимание, что к моменту запроса на отмену количество соответствующей заявки могло быть уже частично уменьшено или заявка могла стать неактивной. Запросы на отмену неактивной заявки не изменяют ничего в книге заявок.
На каждое входящее сообщение книга заявок должна генерировать все сделки, которые оно вызывает, и текущую котировку (размер предложения, цена предложения, размер спроса, цена спроса) после обработки соответствующего сообщения, даже если в результате этого сообщения ничего не изменилось в книге заявок. Таким образом, количество котировок, которые генерирует книга заявок, всегда равно количеству входящих сообщений.
Входные данные
Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ 10000) — количество входящих сообщений, которые должна обработать книга заявок. Следующие n строк содержат сообщения. Каждая строка начинается с слова, описывающего тип сообщения — BUY, SELL или CANCEL, за которым следует пробел и параметры сообщения.
BUY и SELL обозначают заявку на покупку или продажу соответственно и сопровождаются двумя целыми числами q и p (1 ≤ q ≤ 99999, 1 ≤ p ≤ 99999) — размер заявки и цена. CANCEL обозначает запрос на отмену ранее выданной заявки. За ним следует одно целое число i, которое является номером сообщения с некоторой предшествующей заявкой на покупку или продажу (сообщения нумеруются от 1 до n).
Выходные данные
Выведите поток котировок и сделок, которые генерируют входящие сообщения. Для каждой сделки выведите TRADE, за которым следует пробел и размер сделки и цена. Для каждой котировки выведите QUOTE, за которым следует пробел и размер предложения, цена предложения, знак минус ("-"), размер спроса, цена спроса (все разделены пробелами).
Существует особый случай, когда в книге заявок нет активных заявок на покупку или продажу (предложение и/или спрос не определены). Этот случай обрабатывается следующим образом. Если нет активной заявки на покупку, то предполагается, что размер предложения равен нулю, а цена предложения равна нулю. Если нет активной заявки на продажу, то предполагается, что размер спроса равен нулю, а цена спроса равна 99999. Обратите внимание, что ноль не является легальной ценой, но 99999 является легальной ценой. Получатель сообщений котировок различает фактическую цену спроса 99999 от особого случая отсутствия заявок на продажу, глядя на размер спроса.
См. пример для дальнейшего разъяснения.