Stock Prices#2456

Statement Discussion

Stock Prices

1 second

64 megabytes

Very easy

In this problem, we deal with the calculation of stock prices. You need to know the following terms regarding stock prices:

The ask price is the lowest price at which someone is willing to sell a share.
The bid price is the highest price at which someone is willing to buy a share.
The stock price is the price at which the last deal occurred.

Whenever the bid price is greater than or equal to the ask price, a deal is established. A buy order offering the bid price is matched with a sell order at the ask price, and shares are exchanged at the ask price until either the sell order or the buy order (or both) is fully executed (i.e., the buyer wants no more shares, or the seller has no more shares to sell). You will be given a list of orders (either buy or sell), and after each order you must determine the current ask price, bid price, and stock price after all possible deals have taken place.

Input

The first line contains a positive integer: the number of test cases, at most $100$ . For each test case:

One line with an integer $n$ (1 \leq n \leq 1000): the number of orders.
$n$ lines of the form "order type $x$ shares at $y$ ", where order type is either "buy" or "sell", $x$ (1 \leq x \leq 1000) is the number of shares someone wishes to buy or sell, and $y$ (1 \leq y \leq 1000) is the desired price.

Output

For each test case:

$n$ lines, each of the form "a_i b_i s_i", where a_i, b_i, and s_i are the current ask, bid, and stock prices, respectively, after the $i$ -th order has been processed and all possible deals have taken place. Whenever a price is not defined, output "-" instead of the price.

Examples

Example 1

Loading

Loading

1 \leq n \leq 1000

1 \leq x \leq 1000

1 \leq y \leq 1000

a_{i}

b_{i}

s_{i}

a_{i}

b_{i}

s_{i}