거래소

여러분은 거래소의 핵심 엔진인 호가창(order book) 을 구현합니다. 거래소에서는 여러 자원과 상품이 공개 경매로 거래되며, 각 자원·상품은 서로 독립적으로 거래되고 종류마다 별도의 호가창 인스턴스가 존재합니다. 올바른 주문을 호가창에 넣는 일은 여러분의 몫이 아닙니다. 여러분이 작성하는 호가창은 거래소 시스템의 나머지 부분으로부터 적절한 주문들을 스트림으로 전달받습니다.

호가창은 메시지 스트림을 받습니다. 메시지는 주문이거나, 이전에 제출된 주문을 취소하라는 요청입니다. 취소되지 않은 주문을 활성(active) 주문이라고 합니다. 주문에는 매수(buy) 주문과 매도(sell) 주문이 있습니다. 각 매수·매도 주문은 양의 수량과 양의 가격을 가집니다. 호가창은 활성 주문 목록을 관리하며 호가(quote) 와 체결(trade) 을 생성합니다.

가장 높은 가격의 활성 매수 주문을 최우선 매수 주문이라 하고, 그 가격을 매수 호가(bid price) 라 합니다. 가장 낮은 가격의 활성 매도 주문을 최우선 매도 주문이라 하고, 그 가격을 매도 호가(ask price) 라 합니다. 매도 호가는 항상 매수 호가보다 높습니다. 즉, 매수자는 매도자가 받고자 하는 금액보다 적게 지불하려 합니다.

호가창의 현재 호가는 현재 매수 수량, 매수 호가, 매도 수량, 매도 호가로 이루어집니다. 여기서 매수 수량과 매도 수량은 각각 현재 매수 호가와 현재 매도 호가에 있는 모든 활성 주문의 수량 합입니다.

체결은 매수자와 매도자 사이의 거래를 기록합니다. 각 체결은 수량과 가격을 가집니다.

매수 주문이 현재 매도 호가 이상의 가격으로 도착하면 해당 주문들이 매칭되어 체결이 발생합니다 — 매수자와 매도자가 가격에 합의한 것입니다. 반대로 매도 주문이 현재 매수 호가 이하의 가격으로 도착해도 체결이 발생합니다. 매칭에서 같은 가격의 주문들에 대해 호가창은 FIFO(선입선출) 큐처럼 동작합니다(자세한 내용은 아래 참고).

매수 주문이 현재 매도 호가 이상의 가격으로 도착하면 곧바로 호가창에 등록되지 않습니다. 먼저 여러 체결이 생성되며, 이 과정에서 들어온 주문의 수량이 줄어들 수 있습니다. 체결은 들어온 매수 주문과 최우선 매도 주문 사이에서 생성됩니다. 최우선 주문이 여러 개(매도 호가에 여러 주문)이면 호가창에 먼저 들어온 주문이 선택됩니다. 체결은 현재 매도 호가로 생성되며, 체결 수량은 매칭되는 두 주문 수량 중 작은 값입니다. 매칭된 두 주문의 수량은 체결 수량만큼 줄어듭니다. 이로 인해 매도 주문의 수량이 0이 되면 그 주문은 비활성화되어 호가창에서 제거됩니다. 들어온 매수 주문의 수량이 0이 되면 과정이 끝나고 들어온 주문은 비활성 상태가 됩니다. 들어온 매수 주문의 수량이 아직 양수이고 매칭할 다른 매도 주문이 남아 있으면, 새로운 매도 호가로 체결을 계속 생성합니다(매도 주문이 소진되어 비활성화되면서 매도 호가가 올라갈 수 있습니다). 매칭할 매도 주문이 더 이상 없으면(현재 매도 호가가 들어온 매수 주문의 가격보다 커지면), 들어온 매수 주문은 남은 수량으로 호가창에 등록됩니다.

들어온 매도 주문도 대칭적으로 동작합니다. 호가창의 매수 주문들과 매칭되며, 체결은 매수 호가로 생성됩니다.

취소 요청이 오면 해당 주문은 호가창에서 그대로 제거되어 비활성화됩니다. 취소 요청 시점에는 해당 주문의 수량이 이미 일부 줄어 있거나, 주문이 이미 비활성 상태일 수도 있습니다. 이미 비활성인 주문을 취소하는 요청은 호가창에 아무런 변화를 주지 않습니다.

들어오는 모든 메시지에 대해, 호가창은 그 메시지가 일으키는 모든 체결을 생성한 뒤, 그 메시지를 처리한 후의 현재 호가(매수 수량, 매수 호가, 매도 수량, 매도 호가)를 생성해야 합니다 — 그 메시지의 결과로 아무것도 바뀌지 않았더라도 마찬가지입니다. 따라서 호가창이 생성하는 호가의 개수는 항상 들어오는 메시지의 개수와 같습니다.

첫 번째 줄에는 정수 $n$ ($1 \le n \le 10,000$)이 주어집니다. 호가창이 처리해야 하는 메시지의 개수입니다. 이어지는 $n$개의 줄에는 각각 하나의 메시지가 주어집니다. 각 줄은 메시지 유형을 나타내는 단어 — BUY, SELL, CANCEL — 로 시작하고, 공백에 이어 매개변수가 옵니다.

BUY와 SELL은 각각 매수·매도 주문을 뜻하며, 각각 두 정수 $q$와 $p$ ($1 \le q \le 99,999$, $1 \le p \le 99,999$)가 뒤따릅니다 — 주문 수량과 가격입니다. CANCEL은 이전에 제출된 주문을 취소하는 요청으로, 하나의 정수 $i$가 뒤따릅니다. $i$는 매수 또는 매도 주문을 낸 이전 메시지의 번호입니다(메시지는 $1$부터 $n$까지 번호가 매겨집니다).

들어오는 메시지들이 생성하는 호가와 체결의 스트림을 출력하세요. 각 체결에 대해서는 TRADE 뒤에 공백, 체결 수량, 체결 가격을 출력합니다. 각 호가에 대해서는 QUOTE 뒤에 매수 수량, 매수 호가, 빼기 기호(-), 매도 수량, 매도 호가를 (모두 하나의 공백으로 구분하여) 출력합니다.

활성 매수 주문이나 매도 주문이 하나도 없는 특수한 경우(매수 호가와/또는 매도 호가가 정의되지 않는 경우)가 있습니다. 활성 매수 주문이 없으면 매수 수량은 $0$, 매수 호가는 $0$으로 간주합니다. 활성 매도 주문이 없으면 매도 수량은 $0$, 매도 호가는 $99,999$로 간주합니다. $0$은 유효한 가격이 아니지만 $99,999$는 유효한 가격입니다. 받는 쪽은 매도 수량을 보고 실제 매도 호가 $99,999$와 "매도 주문이 없는" 경우를 구별합니다. 자세한 것은 예제를 참고하세요.