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.


-----Input-----

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.


-----Output-----

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.


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

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



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3
import collections

n, s = list(map(int, input().split()))

buy_orders = collections.defaultdict(int)
sell_orders = collections.defaultdict(int)

for i in range(n):
    d, p, q = input().split()
    p, q = int(p), int(q)

    if d == 'B':
        buy_orders[p] += q
    else:
        sell_orders[p] += q

buy_orders = sorted(list(buy_orders.items()), reverse=True)
sell_orders = sorted(list(sell_orders.items()), reverse=True)

for order in sell_orders[-s:]:
    print('S', order[0], order[1])
for order in buy_orders[:s]:
    print('B', order[0], order[1])


__author__ = 'Andrey'
n, s = list(map(int, input().split()))
B = dict()
S = dict()
for i in range(n):
    t = input().split()
    if t[0] == "B":
        B[int(t[1])] = B.get(int(t[1]), 0) + int(t[2])
    else:
        S[int(t[1])] = S.get(int(t[1]), 0) + int(t[2])
B_keys = sorted(list(B.keys()), reverse=True)
S_keys = sorted(S.keys())
if B_keys:
    b_s = B_keys[min(s - 1, len(B_keys) - 1)]
if S_keys:
    s_s = S_keys[min(s - 1, len(S_keys) - 1)]
    for key_1 in sorted(list(S.keys()), reverse=True):
        if key_1 <= s_s:
            print("S", key_1, S[key_1])
if B_keys:
    b_s = B_keys[min(s - 1, len(B_keys) - 1)]
    for key_2 in sorted(list(B.keys()), reverse=True):
        if key_2 >= b_s:
            print("B", key_2, B[key_2])


import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict, deque

# Guide:
#   1. construct complex data types while reading (e.g. graph adj list)
#   2. avoid any non-necessary time/memory usage
#   3. avoid templates and write more from scratch
#   4. switch to "flat" implementations

def VI(): return list(map(int,input().split()))
def I(): return int(input())
def LIST(n,m=None): return [0]*n if m is None else [[0]*m for i in range(n)]


def main(info=0):
    n,s = VI()
    d,p,q = LIST(n), LIST(n), LIST(n)
    db = {}
    ds = {}
    for i in range(n):
        d[i], p[i], q[i] = input().split()
    p = [int(x) for x in p]
    q = [int(x) for x in q]
    for i in range(n):
        if d[i]=='B':
            if p[i] in db:
                db[p[i]] = db[p[i]] + q[i]
            else:
                db[p[i]] = q[i]
        if d[i]=='S':
            if p[i] in ds:
                ds[p[i]] = ds[p[i]] + q[i]
            else:
                ds[p[i]] = q[i]
    lb = sorted(list(db.items()))[::-1][:s]
    ls = sorted(list(ds.items()))[:s][::-1]

    for k,v in ls:
        print("S {} {}".format(k,v))
    for k,v in lb:
        print("B {} {}".format(k,v))


def __starting_point():
    main()

__starting_point()

n, s2 = map(int, input().split())
b = {}
s = {}
b1 = set()
s1 = set()
for i in range(n):
    v = list(map(str, input().split()))
    if v[0] == 'B':
        if v[1] in b1:
            b[v[1]] += int(v[2])
        else:
            b[v[1]] = int(v[2])
            b1.add(v[1])
    if v[0] == 'S':
        if v[1] in s1:
            s[v[1]] += int(v[2])
        else:
            s[v[1]] = int(v[2])
            s1.add(v[1])
ansb = []
anss = []

for i, j in b.items():
    ansb.append((int(i), int(j)))
ansb.sort(reverse = True)

for i, j in s.items():
    anss.append((int(i), int(j)))
anss.sort()
k = len(ansb)
p = len(anss)
i = 0
j = min(s2 - 1, p - 1)
s1 = s2

while s1 > 0 and p > 0:
    print('S', anss[j][0], anss[j][1])
    j -= 1
    s1 -= 1
    p -= 1


while s2 > 0 and k > 0:
    print('B', ansb[i][0], ansb[i][1])
    k -= 1
    s2 -= 1
    i += 1

n, s = map(int, input().split())
pricesell = dict()
pricebuy = dict()
sellp = set()
buyp = set()
for i in range(n):
    tmp = input().split()
    if tmp[0] == "B":
        if int(tmp[1]) in buyp:
            pricebuy[int(tmp[1])] += int(tmp[2])
        else:
            pricebuy[int(tmp[1])] = int(tmp[2])
        buyp.add(int(tmp[1]))
    else:
        if int(tmp[1]) in sellp:
            pricesell[int(tmp[1])] += int(tmp[2])
        else:
            pricesell[int(tmp[1])] = int(tmp[2])
        sellp.add(int(tmp[1]))
buy = list(pricebuy.items())
sell = list(pricesell.items())
buy.sort(reverse=True)
sell.sort()
buy1 = buy[:min(s, len(buy))]
sell1 = sell[:min(s, len(sell))]
sell1.sort(reverse=True)
buy1 = list(map(lambda x: "B " + str(x[0]) + " " + str(x[1]), buy1))
sell1 = list(map(lambda x: "S " + str(x[0]) + " " + str(x[1]), sell1))
print(*sell1, sep="\n")
print(*buy1, sep="\n")

n,z=map(int,input().split())
b=[]
s=[]
for i in range(n):
	h=input().split()
	if h[0]=="B":
		bb=True
		for j in range(len(b)):
			(x,y)=b[j]
			if x==int(h[1]):
				b[j]=(x,y+int(h[2]))
				bb=False
		if bb:b+=[(int(h[1]),int(h[2]))]
	else:
		bb=True
		for j in range(len(s)):
			(x,y)=s[j]
			if x==int(h[1]):
				s[j]=(x,y+int(h[2]))
				bb=False
		if bb:s+=[(int(h[1]),int(h[2]))]

b=sorted(b,key=lambda colonnes:colonnes[0])
s=sorted(s,key=lambda colonnes:colonnes[0])

i=0
h=0
while h<z and len(s)-1-i>=0:
	if len(s)-1-i<z:
		print("S",s[len(s)-1-i][0],s[len(s)-1-i][1])
		h+=1
	i+=1
for i in range(z):
	if len(b)-1-i>=0:print("B",b[len(b)-1-i][0],b[len(b)-1-i][1])

n, s = map(int, input().split())
buy = dict()
sell = dict()
for i in range(n):
    d, p, q = map(str, input().split())
    p = int(p)
    q = int(q)
    if d == 'B':
        if p in buy:
            buy[p] += q
        else:
            buy[p] = q
    else:
        if p in sell:
            sell[p] += q
        else:
            sell[p] = q        
bk = list(buy.keys())
bv = list(buy.values())
bl = list(zip(bk, bv))
sk = list(sell.keys())
sv = list(sell.values())
sl = list(zip(sk, sv))
bl.sort(reverse = True)
sl.sort()
bb = len(bl)
ss = len(sl)

if s > ss:
    sl.sort(reverse = True)
    for i in range(ss):
        print('S', sl[i][0], sl[i][1])
else:
    sl.sort()
    for i in range(s - 1, -1, -1):
            print('S', sl[i][0], sl[i][1])  
            
if s > bb:
    for i in range(bb):
        print('B', bl[i][0], bl[i][1])
else:
    for i in range(s):
            print('B', bl[i][0], bl[i][1])    

import operator

n,s=list(map(int,input().split()))
orders=[]
for i in range(n):
	orders.append(tuple(map(str,input().split()))) #d,p,q

aggr={}
for order in orders:
	key=(order[0][0],int(order[1]))
	if key not in aggr:
		aggr[key]=0
	aggr[key]+=int(order[2]) #volume

books={"B":[],"S":[]}
for key in aggr:
	book=books[key[0]]
	volume=aggr[key]
	book.append((key[0],key[1],volume)) #d,p,q


for k in books:
	books[k]=list(reversed(sorted(books[k],key=operator.itemgetter(1))))

lenB=len(books["S"])
for i in range(min(lenB,s)):
	order=books["S"][max(0,lenB-s)+i]
	print("S %d %d" %(order[1],order[2]))

for i in range(min(len(books["B"]),s)):
	order=books["B"][i]
	print("B %d %d" %(order[1],order[2]))









from sys import stdin,stdout
input = stdin.readline

b = {}
s = {}

n, l = map(int,input().split(' '))
for i in range(n):
    d,p,q = input().split(' ')
    p,q = int(p),int(q)
    if d == 'B':
        try:
            b[p] += q
        except KeyError:
            b[p] = q
    else:
        try:
            s[p] += q
        except KeyError:
            s[p] = q

for key in sorted(sorted(s)[0:min(l,len(s))],reverse=True):
    print("S %s %s" % (key, s[key]))

for key in sorted(b,reverse=True)[0:min(l,len(b))]:
    print("B %s %s" % (key, b[key]))

B = [0] *  (10 ** 5 + 2)
S = [0] * (10 ** 5 + 2)
a, b = list(map(int, input().split()))
for i in range(a):
    l = list(map(str, input().split()))
    if l[0] == 'S':
        S[int(l[1])] += int(l[2])
    if l[0] == 'B':
        B[int(l[1])] += int(l[2])
count = 0
ans = []
for i in range(10 ** 5 + 2):
    if S[i] != 0:
        count += 1
        ans.append(('S', i, S[i]))
        if count == b:
            break    
for i in range(len(ans) - 1, -1, -1):
    print(ans[i][0], ans[i][1], ans[i][2])
count = 0
for i in range(10 ** 5 + 1, -1, -1):
    if B[i] != 0:
        count += 1
        print('B', i, B[i])
        if count == b:
            break


n,s=[int(x) for x in input().split()]
ordenes = {}
for i in range(n):
    d,p,q=input().split()
    head = d + " " + p
    p,q=int(p),int(q)
    if head not in ordenes:
        ordenes[head]=0
    ordenes[head]+=q

ventas = {}
compras = {}

for i in ordenes:
    if i[0]=="B":
        compras[int(i[2:])]=str(ordenes[i])
    else:
        ventas[int(i[2:])]=str(ordenes[i])

listacompras=list(compras.keys())
listaventas = list(ventas.keys())
listacompras.sort(reverse=True)
listaventas.sort(reverse=True)

for i in range(-s,0):
    if i<-len(ventas):
        continue
    print("S "+str(listaventas[i])+" "+str(ventas[listaventas[i]]))


for i in range(s):
    if i>=len(compras):
        break
    print("B "+str(listacompras[i])+" "+str(compras[listacompras[i]]))


n,s = [int(x) for x in input().split()]
buy_dict = {}
sell_dict = {}
for i in range(n):
	chtype,pi,di = input().split()
	pi = int(pi)
	di = int(di)
	if chtype=='B':
		buy_dict[pi] = buy_dict.get(pi,0)+di
	else:
		sell_dict[pi] = sell_dict.get(pi,0)+di
buy_list = sorted(list(buy_dict.items()),reverse=True)[:s]
sell_list = reversed(sorted(sell_dict.items())[:s])
for pi,qi in sell_list:
	print('S',pi,qi)
for pi,qi in buy_list:
	print('B',pi,qi)


n, s = list(map(int, input().split()))
B = []
S = []
for i in range(n):
    st = list(input().split())
    st[1], st[2] = int(st[1]), int(st[2])
    if st[0] == 'B':
        B.append(st)
    else:
        S.append(st)
B.sort()
S.sort()
i = 0
while i < len(B) - 1:
    if B[i][1] == B[i + 1][1]:
        B[i][2] += B[i + 1][2]
        del(B[i + 1])
    else:
        i += 1
i = 0
while i < len(S) - 1:
    if S[i][1] == S[i + 1][1]:
        S[i][2] += S[i + 1][2]
        del(S[i + 1])
    else:
        i += 1
B.reverse()
b = []
for i in range(min(s, len(S))):
    b.append(S[i])
b.reverse()
for i in range(len(b)):
    print(*b[i])
for i in range(min(s, len(B))):
    print(*B[i])

import heapq


n, s = map(int, input().split())
applications_sell = []
applications_buy = []

for i in range(n):
    cur1, cur2, cur3 = map(str, input().split())
    if cur1 == 'S':
        heapq.heappush(applications_sell, [cur1, int(cur2), int(cur3)])
    else:
        heapq.heappush(applications_buy, [cur1, -int(cur2), int(cur3)])

glass_sell = []
if len(applications_sell):
    glass_sell.append(heapq.heappop(applications_sell))

while len(applications_sell) > 0:
    cur = heapq.heappop(applications_sell)
    if glass_sell[-1][1] == cur[1]:
        glass_sell[-1][2] += cur[2]
    else:
        glass_sell.append(cur)

glass_buy = []    
if len(applications_buy):
    glass_buy.append(heapq.heappop(applications_buy))

while len(applications_buy) > 0:
    cur = heapq.heappop(applications_buy)
    if glass_buy[-1][1] == cur[1]:
        glass_buy[-1][2] += cur[2]
    else:
        glass_buy.append(cur)

for i in range(min(len(glass_sell), s) - 1, -1, -1):
    print(glass_sell[i][0], glass_sell[i][1], glass_sell[i][2])

for i in range(min(len(glass_buy), s)):
    print(glass_buy[i][0], -glass_buy[i][1], glass_buy[i][2])

n,s=list(map(int,input().split()))
sem=[-1]*(100001)
bum=[-1]*(100001)
for i in range(n):
    wh,p,q=input().split()
    p=int(p)
    q=int(q)
    if wh=='B':
        if bum[p]==-1:
            bum[p]=0
        bum[p]+=q
    else:
        if sem[p]==-1:
            sem[p]=0
        sem[p]+=q
fins=[]
finb=[]
ts=s
for i in range(100000,-1,-1):
    if not ts:
        break
    if(bum[i]!=-1):
        finb.append((i,bum[i]))
        ts-=1
ts=s
for i in range(100001):
    if not ts:
        break
    if(sem[i]!=-1):
        fins.append((i,sem[i]))
        ts-=1
ts=s
for i in range(len(fins)-1,-1,-1):
    if not ts:
        break
    a,b=fins[i]
    print('S',a,b)
    ts-=1
ts=s
for i in range(len(finb)):
    if not ts:
        break
    a,b=finb[i]
    print('B',a,b)
    ts-=1











n, ss = map(int, input().split())
buy, send = dict(), dict()
for i in range(n):
    s = list(map(str, input().split()))
    c_v = list(map(int, s[1:]))
    if s[0] == 'B':
        if c_v[0] in buy:
            buy[c_v[0]] += c_v[1]
        else:
            buy[c_v[0]] = c_v[1]
    else:
        if c_v[0] in send:
            send[c_v[0]] += c_v[1]
        else:
            send[c_v[0]] = c_v[1]
length_s, length_b = len(send), len(buy)
buy_ = sorted(buy)[0 if length_b < ss else length_b - ss:]
send_ = sorted(send)[:min(length_s, ss)]
for i in range(len(send_) - 1, -1, -1):
    print('S', send_[i], send[send_[i]])
for i in range(len(buy_) - 1, -1, -1):
    print('B', buy_[i], buy[buy_[i]])

n, s = list(map(int, input().split()))
buy = {}
sale = {}
for i in range(n):
    cur = input().split()
    p = int(cur[1])
    q = int(cur[2])
    if cur[0] == 'B':
        if p in buy:
            buy[p] += q
        else:
            buy[p] = q
    else:
        if p in sale:
            sale[p] += q
        else:
            sale[p] = q

items = list(sale.items())
items.sort()
items = items[:s]
items.reverse()
for i in items:
    print('S', i[0], i[1])
    
items = list(buy.items())
items.sort()
items.reverse()
c = 0
for i in items:
    if c == s:
        break
    print('B', i[0], i[1])
    c += 1


n, s = (list(map(int, input().split())))

buyorder = []
sellorder = []

for i in range(n):
    line = input()
    order = line.split()
    order[1] = int(order[1])
    order[2] = int(order[2])

    if order[0] == "B" :
        for m in buyorder:
            if m[1] == order[1]:
                m[2] += order[2]
                break
        else:
            buyorder.append(order)
    else:
        for m in sellorder:
            if m[1] == order[1]:
                m[2] += order[2]
                break
        else:
            sellorder.append(order)


buyorder.sort(key= lambda data : data[1], reverse = True)
sellorder.sort(key= lambda data : data[1], reverse = False)

if len(sellorder)<s:
    sellorder.sort(key= lambda data : data[1], reverse = True)
    for i in sellorder:
        print(i[0], i[1], i[2])
else:
    newsell = []
    for i in range(s):
        newsell.append(sellorder[i])
    newsell.sort(key= lambda data : data[1], reverse = True)
    for i in range(s):
        print(newsell[i][0], newsell[i][1], newsell[i][2])

if len(buyorder)<s:
    for i in buyorder:
        print(i[0], i[1], i[2])
else:
    for i in range(s):
        print(buyorder[i][0], buyorder[i][1], buyorder[i][2])


n, deaph = map(int, input().split())
buy = [0] * (10 ** 5 + 1)
sell = [0] * (10 ** 5 + 1)
for i in range(n):
    s = input()
    t = s[0]
    c, v = map(int, s[2:].split())
    if t == "B":
        buy[c] += v
    elif t == "S":
        sell[c] += v


ans_sell = []
cnt = 0
i = 0
while cnt < deaph and i < len(sell):
    if sell[i] != 0:
        ans_sell.append((i, sell[i]))
        cnt += 1
    i += 1
for i in range(len(ans_sell)-1, 0-1, -1):
    print("S", ans_sell[i][0], ans_sell[i][1])

cnt = 0
i = len(buy) - 1
while cnt < deaph and i >= 0:
    if buy[i] != 0:
        print("B", i, buy[i])
        cnt += 1
    i -= 1

n, s = map(int, input().split())
buys = dict()
sell = dict()
for _ in range(n):
  f = input().split()
  if (f[0] == "B"):
    buys[int(f[1])] = buys.get(int(f[1]), 0) + int(f[2])
  else:
    sell[int(f[1])] = sell.get(int(f[1]), 0) + int(f[2])
bres = sorted(buys.keys(), reverse = True)
sres = sorted(sell.keys())
if bres:
  bs = bres[min(s - 1, len(bres) - 1)]
if sres:
  ss = sres[min(s - 1, len(sres) - 1)]
  for key in sorted(sell.keys(), reverse = True):
    if (key <= ss):
      print("S", key, sell[key])
if bres:
  bs = bres[min(s - 1, len(bres) - 1)]
  for key in sorted(buys.keys(), reverse = True):
    if (key >= bs):
      print("B", key, buys[key])

s = input()
n, d = int(s.split()[0]), int(s.split()[1])
b, s = {}, {}
wb, ws = [], []
for i in range(0, n):
	st = input().split()
	st[1] = int(st[1])
	st[2] = int(st[2])
	if st[0] == 'B':
		if st[1] not in b:
			b[st[1]] = st[2]
		else:
			b[st[1]] += st[2];
		if st[1] not in wb:
			wb.append(st[1]);
	else:
		if st[1] not in s:
			s[st[1]] = st[2]
		else:
			s[st[1]] += st[2];
		if st[1] not in ws:
			ws.append(st[1]);
ws.sort()#[:d]#.sort(reverse=True)
wb.sort(reverse=True)#[:d]
ws = ws[:d]
wb = wb[:d]
ws.sort(reverse=True)
for i in ws:
	print('S %s %s' %(i, s[i]))
for i in wb:
	print('B %s %s' %(i, b[i]))

from collections import defaultdict

n, depth = [int(x) for x in input().split(' ')]
l = []
s = defaultdict(int)
b = defaultdict(int)
sl = []
bl = []
for i in range(n) :
    d, p, q = [x for x in input().split(' ')]
    p = int(p)
    q = int(q)
    if d == 'S' : s[p] += q
    else : b[p] += q

for p, q in list(s.items()): sl += [(p, q)]
for p, q in list(b.items()): bl += [(p, q)]

sl.sort()
bl.sort()
sp = ["S {0} {1}".format(i[0], i[1]) for i in sorted(sl[0:depth], key=lambda x: -x[0])]
bp = ["B {0} {1}".format(i[0], i[1]) for i in bl[-1:-depth-1:-1]]

for i in (sp + bp) : print(i)


from collections import defaultdict
n, s = [int(s) for s in input().split()]
buyq = defaultdict(int)
selq = defaultdict(int)
sq = 0
bq = 0
for i in range(n):
    d, p, q = input().split()
    p = int(p)
    q = int(q)
    if d == 'B':
        buyq[p] += q
    else:
        selq[p] += q
a = sorted(selq.keys())
for i in a[min(s, len(selq))-1::-1]:
    print("S", i, selq[i])

b = sorted(buyq.keys())
for i in b[::-1][:min(s, len(buyq)):]:
    print("B", i, buyq[i])


import sys
import os
def getint():
    return list(map(int,input().split(' ')))
n,s=getint()
dic={'B':{},'S':{}}
for i in range(n):
    d,p,q=list(input().split(' '))
    p=int(p)
    q=int(q)
    dic[d][p]=dic[d].get(p,0)+q
for key in sorted(dic['S'],reverse=True)[-s:]:
    print('S',key,dic['S'][key])
for key in sorted(dic['B'],reverse=True)[:s]:
    print('B',key,dic['B'][key])
    #for line in sorted(dic['B'])[:s]:
        #print('B',line)