Exchange

You are building the core engine of an exchange — its order book. Different resources and commodities are traded on the exchange through public auction. Each resource or commodity is traded independently, and there is a separate order book instance for each one. Getting the correct orders into the book is not your concern; the order book you write receives a stream of appropriate orders from the rest of the exchange system.

The order book receives a stream of messages. A message is either an order or a request to cancel a previously issued order. Orders that have not been cancelled are called active. There are orders to buy and orders to sell. Each buy or sell order has a positive size and a positive price. The order book maintains the list of active orders and generates quotes and trades.

The active buy order with the highest price is the best buy order, and its price is called the bid price. The active sell order with the lowest price is the best sell order, and its price is called the ask price. The ask price is always higher than the bid price — that is, buyers are willing to pay less than sellers want to receive.

A current quote from the order book contains the current bid size, bid price, ask size, and ask price. Here the bid size and ask size are the sums of the sizes of all active orders at the current bid price and the current ask price, respectively.

A trade records a transaction between a buyer and a seller. Each trade has a size and a price.

If a buy order arrives at a price greater than or equal to the current ask price, the corresponding orders are matched and a trade happens — buyer and seller have agreed on a price. Conversely, if a sell order arrives at a price less than or equal to the current bid price, a trade happens as well. For matching, the order book behaves like a FIFO queue for orders at the same price (details below).

When a buy order arrives at a price greater than or equal to the current ask price, it is not entered into the book immediately. First, a number of trades is generated, possibly reducing the size of the incoming order. A trade is generated between the incoming buy order and the best sell order. If there are several best orders (at the ask price), the one that entered the book first is chosen. The trade is generated at the current ask price, with its size equal to the smaller of the two matching orders' sizes. Both matching orders are reduced by the trade size. If this reduces the sell order's size to zero, it becomes inactive and is removed from the book. If the incoming buy order's size becomes zero, the process ends and the incoming order becomes inactive. If the incoming buy order still has positive size and another sell order is available to match, the process continues, generating further trades at the new ask price (the ask price can rise as sell orders are consumed and become inactive). If no sell order is left to match (the current ask price has become greater than the incoming buy order's price), the incoming buy order is added to the book with its remaining size.

An incoming sell order behaves symmetrically: it is matched against buy orders from the book, and trades are generated at the bid price.

On a cancel request, the corresponding order is simply removed from the book and becomes inactive. Note that by the time of the cancel request the order's size may already have been partially reduced, or the order may already have become inactive. A request to cancel an inactive order changes nothing.

For every incoming message, the order book must generate all trades it causes and then the current quote (bid size, bid price, ask size, ask price) after processing that message — even when nothing changed as a result of the message. Thus the number of quotes the order book generates always equals the number of incoming messages.

The first line contains a single integer $n$ ($1 \le n \le 10,000$) — the number of messages the order book must process. Each of the next $n$ lines contains one message. Each line begins with a word describing the message type — BUY, SELL, or CANCEL — followed by a space and the message parameters.

BUY and SELL denote an order to buy or to sell, respectively, and are each followed by two integers $q$ and $p$ ($1 \le q \le 99,999$, $1 \le p \le 99,999$) — the order size and price. CANCEL denotes a request to cancel a previously issued order; it is followed by a single integer $i$, the number of an earlier message that placed a buy or sell order (messages are numbered from $1$ to $n$).

Print the stream of quotes and trades that the incoming messages generate. For every trade, print TRADE followed by a space, the trade size, and the trade price. For every quote, print QUOTE followed by the bid size, the bid price, a minus sign (-), the ask size, and the ask price (all separated by single spaces).

There is a special case when there are no active buy or sell orders (the bid and/or ask is undefined). If there is no active buy order, the bid size is taken to be $0$ and the bid price $0$. If there is no active sell order, the ask size is taken to be $0$ and the ask price $99,999$. Note that $0$ is not a legal price, but $99,999$ is; the recipient distinguishes a genuine ask price of $99,999$ from the "no sell orders" case by looking at the ask size. See the examples for further clarification.