Order Book

题意翻译

有$n$ 个记录，其中每个记录包含两个信息$p_i,q_i$ ，表示交易单品金额和交易数量。现在需要把这些记录做成清单。规则如下： 1. 把$p_i$ 相同的记录合并，$q_i$ 取这些记录中原有的$q_i$ 之和。 2. 合并之后，输出卖出记录（`S`）中的$p_i$ 最小的$s$ 条记录，按照$p_i$ **降序输出**。 3. 合并之后，输出买入记录（`B`）中的$p_i$ 最大的$s$ 条记录，按照$p_i$ **降序输出**。 其中（2）（3）条的格式是$opt\;p_i\;q_i$ ，$opt$ 是`S`和`B`中的一个。记录不足$s$ 条只要输出所有的即可。

题目描述

In this task you need to process a set of stock exchange orders and use them to create order book. An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number $ i $ has price $ p_{i} $ , direction $ d_{i} $ — buy or sell, and integer $ q_{i} $ . This means that the participant is ready to buy or sell $ q_{i} $ stocks at price $ p_{i} $ for one stock. A value $ q_{i} $ is also known as a volume of an order. All orders with the same price $ p $ and direction $ d $ are merged into one aggregated order with price $ p $ and direction $ d $ . The volume of such order is a sum of volumes of the initial orders. An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order. An order book of depth $ s $ contains $ s $ best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than $ s $ aggregated orders for some direction then all of them will be in the final order book. You are given $ n $ stock exhange orders. Your task is to print order book of depth $ s $ for these orders.

输入输出格式

输入格式

The input starts with two positive integers $ n $ and $ s $ ( $ 1<=n<=1000,1<=s<=50 $ ), the number of orders and the book depth. Next $ n $ lines contains a letter $ d_{i} $ (either 'B' or 'S'), an integer $ p_{i} $ ( $ 0<=p_{i}<=10^{5} $ ) and an integer $ q_{i} $ ( $ 1<=q_{i}<=10^{4} $ ) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.

输出格式

Print no more than $ 2s $ lines with aggregated orders from order book of depth $ s $ . The output format for orders should be the same as in input.

输入输出样例

输入样例 #1

6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10

输出样例 #1

S 50 8
S 40 1
B 25 10
B 20 4

说明

Denote (x, y) an order with price $ x $ and volume $ y $ . There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample. You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.