Practice Coding with the exercise "Wall Street"

Statement

Goal

On Wall Street people buy and people sell.
When a buyer and a seller's prices match a trade is created.
When there is no match the order is “put in the book”.

Some special cases that must be considered:
- If the buyer's price is higher than the seller's price: the price used is the one already in the system.
- If there are more than one order in the system at the same price: a first in first out approach is taken.
- A trade cannot be concluded between orders that aren't on top of the book: the best price is always traded first. For a buy order the best price is the highest; for a sell order the best price is the lowest.
- A trade can only occur between orders on the same stock symbol.
- If there are remaining quantities after a trade, we try to trade with the next order in the book. If we can't, we put an order “in the book” for the untraded quantity.

An order consist of a symbol that represents the stock to trade, a verb that indicates whether it's a BUY or a SELL, a quantity qty and a price.

Input

Line 1: N number of orders
N following lines: an order as space-separated values: symbol verb qty price

Output

All trades in order of occurrence: symbol qty price
If no trade at all takes place, write NO TRADE

Constraints

2 ≤ N ≤ 1000
1 ≤ qty ≤ 1000
All prices are fixed-point decimals. They must be formatted with minimal integral figures and exactly two fractional figures. (one cent as 0.01)

Example

Input

2
AAA BUY 1 10.00
AAA SELL 1 10.00

Output

AAA 1 10.00

Solve it

A higher resolution is required to access the IDE