빙산 주문

당신은 메타고니아 증권거래소에서 일한다. 메타고니아의 트레이더들이 런던 증권거래소에서 거래되는 빙산 주문을 알게 되어, 같은 기능을 추가해 달라고 고용주에게 요청했다. 거래소는 주문을 받아 체결을 만들어 내는 엔진이다.

빙산 주문은 정수 다섯 개의 조 $(ID, T, P, V, TV)$이다. 각 주문에는 식별자 $ID$(모든 주문에서 서로 다르다), 유형 $T$(BUY = 1 또는 SELL = 2), 가격 $P$, 남은 총 수량 $V$, 팁 수량 $TV$가 있다. 거래소는 주문마다 현재 수량 $CV$와 우선순위 $PR$도 함께 관리한다. 거래소에는 전역 우선순위 카운터 $GP$가 하나 있다. 호가장은 주문의 집합이다.

체결은 정수 네 개의 조 (BUY ID, SELL ID, $P$, $V$)이다. BUY ID와 SELL ID는 서로 체결된 매수 주문과 매도 주문의 식별자이고, $P$는 체결 가격, $V$는 체결 수량이다.

거래소는 주문을 받으면 호가장에 있는 주문과 다음과 같이 맞춘다. 들어온 주문 $a$가 $T_a = SELL$이라고 하자. 호가장에서 $T_b = BUY$이고 $P_b \ge P_a$인 주문 $b$를 찾는다. 그런 주문 중 가격이 가장 큰 것을 고르고, 여럿이면 우선순위가 가장 작은 것을 고른다. 그런 주문 $b$가 있으면 BUY ID $= ID_b$, SELL ID $= ID_a$, 체결 가격 $P_t = P_b$, 체결 수량 $V_t = \min(V_a, CV_b)$인 체결 $t$가 하나 생긴다. 그리고 $V_a$, $V_b$, $CV_b$를 각각 체결 수량만큼 줄인다. 그 결과 $V_b = 0$이 되면 주문 $b$를 호가장에서 제거한다. $V_b > 0$인 채로 $CV_b = 0$이 되면 $CV_b = \min(V_b, TV_b)$로 채우고 $PR_b = GP$로 정한 다음 $GP$를 1 늘린다. $V_a = 0$이 되거나 조건을 만족하는 주문 $b$가 호가장에 더 없을 때까지 $b$를 고르고 체결을 만드는 과정을 반복한다. 후자의 경우 주문 $a$를 $CV_a = \min(V_a, TV_a)$, $PR_a = GP$로 호가장에 넣고 $GP$를 1 늘린다. 주문 $a$의 체결 과정이 끝났을 때 같은 주문 쌍 $a$, $b$ 사이에서 생긴 체결이 여러 개이면(아주 많을 수도 있다) 수량을 모두 더해 하나의 체결로 합친다.

$T_a = BUY$이면 $T_b = SELL$이고 $P_b \le P_a$인 주문 $b$를 찾아 가격이 가장 작은 것, 그중에서 우선순위가 가장 작은 것을 고른다. 나머지 과정은 위와 같고, 체결은 BUY ID $= ID_a$, SELL ID $= ID_b$, $P_t = P_b$, $V_t = \min(V_a, CV_b)$가 된다.

호가장은 처음에 비어 있다. 주문은 하나씩 들어온다. 생성된 체결을 모두 출력하고, 주문을 모두 처리한 뒤의 호가장 상태를 출력하라.

우선순위와 $GP$는 알고리즘을 형식적으로 기술하려고 문제에서 도입한 값이다. 구현에서 이 값을 직접 관리할 필요는 없다. 거래소는 보통 유형별, 가격별로 우선순위 순서대로 정렬한 주문 목록을 유지한다.

첫째 줄에 주문의 개수 $n$이 주어진다 ($1 \le n \le 50000$). 다음 $n$개 줄에는 주문이 하나씩 공백으로 구분된 다섯 정수 $ID$ $T$ $P$ $V$ $TV$로 주어진다. $1 \le ID \le 1000000$이고, 매수 주문이면 $T = 1$, 매도 주문이면 $T = 2$이며, $1 \le P \le 100000$, $1 \le TV \le V \le 1000000000$이다. 모든 식별자는 서로 다르다.

주문마다 그 주문을 처리하면서 생긴 체결을 (BUY ID, SELL ID) 쌍의 오름차순으로 한 줄에 하나씩 출력한다. 각 체결은 공백으로 구분된 네 정수 BUY ID, SELL ID, $P$, $V$로 출력한다. 체결의 총 개수는 100000개를 넘지 않는다. 체결을 모두 출력한 뒤 빈 줄을 하나 출력하고, 이어서 호가장을 출력한다. 호가장에 남은 주문은 공백으로 구분된 여섯 정수 $ID$ $T$ $P$ $V$ $TV$ $CV$로 출력하며, $P$ 순으로 정렬하고 $P$가 같으면 $PR$ 순으로 정렬한다.

첫 번째 예제에서 앞의 네 주문은 $T = BUY$이다. 처음에 $GP$가 1이었다고 하자. 이 네 주문을 받은 뒤 호가장은 $T_b = BUY$ 주문의 매칭 규칙(가격이 큰 것부터, 같으면 우선순위가 작은 것부터)에 따라 다음과 같다.

다섯 번째 주문($ID_a = 4321$)은 $T_a = SELL$, $P_a = 99$, $V_a = 125$이므로 위 네 주문과 모두 체결될 수 있다. 먼저 가격이 가장 높은 101의 주문 1111과 두 번 체결해 수량 30을 채우고, 그 주문을 호가장에서 제거하며 $GP$를 6으로 올리고 $V_a = 95$가 된다. 가격 100에는 세 주문이 남아 있다. 이 세 주문을 한 번 훑으면 체결 세 개가 생겨 수량이 모두 85가 되고(주문 42와 20, 주문 239와 50, 이때 주문 239는 제거된다, 주문 1234와 15), $GP$는 8이 되며 $V_a = 10$이 된다. 이제 호가장은 다음과 같다.

주문 42와 한 번 더 체결해 수량 10을 채우면 주문 42와의 체결 수량은 모두 30이 되고, 주문 4321은 $V_a = 0$으로 끝난다. 주문 4321이 만든 체결 네 개는 예제 출력에 그대로 나온다. 호가장은 다음과 같다.

여섯 번째 주문(매수, $ID = 5678$)은 호가장에 들어가고 $GP$는 9가 된다.

마지막 주문($ID = 8765$)은 가격 조건 때문에 주문 5678과만 체결된다. 수량 30의 체결이 생기고 주문 5678은 제거되며 주문 8765가 호가장에 들어간다. 이제 호가장에는 매수 주문과 매도 주문이 함께 있다.