투자 조사

부업으로 돈을 벌기 위해 최근 Budget Amplifying Profit Coin(BAPC)을 사고파는 암호화폐 거래소를 운영하기 시작했다. 거래소의 인기가 높아지자 정부 규제 당국이 질문을 하기 시작했다. 조사의 일환으로 당국은 거래소에서 이루어진 모든 거래 내역의 목록을 요구했다. 거래 내역은 한 번도 기록해 두지 않았지만, 거래소를 연 이후 접수된 모든 주문 목록은 남아 있다.

거래소는 가격과 수량을 가진 미체결 매수 주문과 매도 주문의 목록을 관리한다. 일반 주문이 들어오면 새로운 최저 매도 가격이 최고 매수 가격 이하인지 확인한다. 이하라면 최저 가격의 매도 주문과 최고 가격의 매수 주문 사이에 거래가 이루어지며, 두 주문 중 적어도 하나는 수량이 전부 채워진다. 가격이 같으면 먼저 들어온 주문부터 체결한다. 최저 매도 가격이 최고 매수 가격보다 커질 때까지 이 과정을 반복한다.

FoK(Fill-or-Kill) 매수 주문이 들어오면, 제시 가격 이하의 미체결 매도 주문만으로 주문 수량을 즉시 전부 채울 수 있어야 한다. 채울 수 있으면 일반 주문과 같은 방식으로 체결한다. 채울 수 없으면 거래 없이 주문 전체를 취소한다. 즉시 이루어지는 한 여러 주문을 합쳐서 FoK 주문을 채워도 된다. FoK 매도 주문도 같은 방식으로 처리하되, 요청 가격 이상의 미체결 매수 주문이 충분해야 한다.

주문이 들어온 순서대로 모든 주문을 처리했을 때, 거래소가 수행한 거래를 모두 나열하라.

첫 줄에 주문 개수 $n$ ($1 \leq n \leq 10^5$)이 주어진다. 이어지는 $n$개의 줄에는 주문이 하나씩 주어진다. 주문의 방향 $s$는 buy 또는 sell이다. 주문 종류 $t$는 normal 또는 fok이다. 1BAPC당 제시하거나 요청하는 가격 $p$ ($1 \leq p \leq 10^9$)와 요청하거나 제시하는 BAPC 수량 $a$ ($1 \leq a \leq 10^9$)가 정수로 주어진다.

거래 횟수를 먼저 출력한다. 이어서 거래가 수행된 순서대로 한 줄에 하나씩 sell 주문 번호, buy 주문 번호, 거래된 BAPC 수량을 출력한다. 주문 번호는 입력에서의 위치이며 1부터 시작한다.