Stock Prices

Time limit1sMemory limit128 MB

Summary

Simulate an order book with buy and sell orders, matching bids and asks at the ask price, and report ask, bid, and last trade price after each order.

Level: Medium5 of 10
Topics: Simulation, Implementation, Queue
Solved: No attempts yet

Problem

In this problem you simulate how a stock price is formed inside a simple order book. Three prices matter:

The ask price is the lowest price at which someone is currently willing to sell one share.
The bid price is the highest price at which someone is currently willing to buy one share.
The stock price is the price at which the most recent deal was made.

Whenever the bid price is greater than or equal to the ask price, a deal is made: a buy order offering the bid price is matched with a sell order asking the ask price, and shares change hands at the ask price until either the buy order or the sell order (or both) is completely filled. This matching keeps repeating while the highest bid is at least the lowest ask. You are given a sequence of orders, each either a buy or a sell; after processing every order, report the current ask price, bid price, and stock price.

Input

The first line contains a positive integer, the number of test cases (at most $100$ ). Each test case is given as:

One line with an integer $n$ ( $1 \le n \le 1000$ ): the number of orders.
$n$ lines, each of the form buy x shares at y or sell x shares at y. Here buy means a buy order and sell a sell order, $x$ ( $1 \le x \le 1000$ ) is the number of shares, and $y$ ( $1 \le y \le 1000$ ) is the desired price.

Output

For each test case output $n$ lines. The $i$ -th line contains three values a b s separated by single spaces: the current ask price, bid price, and stock price after the $i$ -th order has been processed and every possible deal has been made. If a price is not defined, print - in its place. Every test case starts with all three prices undefined.

Examples6

Example 1

Input

2
6
buy 10 shares at 100
sell 1 shares at 120
sell 20 shares at 110
buy 30 shares at 110
sell 10 shares at 99
buy 1 shares at 120
6
sell 10 shares at 100
buy 1 shares at 80
buy 20 shares at 90
sell 30 shares at 90
buy 10 shares at 101
sell 1 shares at 80

Expected output

- 100 -
120 100 -
110 100 -
120 110 110
120 100 99
- 100 120
100 - -
100 80 -
100 90 -
90 80 90
100 80 90
100 - 80

Example 2

Input

1
3
buy 5 shares at 50
buy 3 shares at 60
buy 2 shares at 55

Expected output

- 50 -
- 60 -
- 60 -

Example 3

Input

1
3
sell 5 shares at 50
sell 3 shares at 40
sell 2 shares at 45

Expected output

50 - -
40 - -
40 - -

Example 4

Input

1
2
buy 10 shares at 100
sell 10 shares at 100

Expected output

- 100 -
- - 100

Example 5

Input

1
4
sell 5 shares at 100
sell 5 shares at 110
sell 5 shares at 120
buy 12 shares at 130

Expected output

100 - -
100 - -
100 - -
120 - 120

Example 6

Input

1
3
buy 4 shares at 100
buy 6 shares at 100
sell 8 shares at 100

Expected output

- 100 -
- 100 -
- 100 100