Description

你正在为 Metagonia 证券交易所工作。最近，Metagonia 的交易员听说了伦敦证券交易所的冰山订单，并要求你的雇主也增加这种功能。证券交易所是一个接收订单并生成交易的引擎。

冰山订单是一个五元组整数 (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。在所有当前订单簿上的订单中，我们寻找一个订单 $b$，使得 $T_{b} =$ BUY 且 $P_{b} \ge P_{a}$。我们选择这样的订单 $b$，其价格最大，如果有多个，则选择优先级最小的。如果存在这样的订单 $b$，则生成交易 $t$，其 BUY $ID_{t} = ID_{b}$ 和 SELL $ID_{t} = ID_{a}$，交易价格 $P_{t} = P_{b}$，交易量 $V_{t} = \min(V_{a}, CV_{b})$。$V_{a}, V_{b},$ 和 $CV_{b}$ 都减少交易量。如果 $V_{b} = 0$ 之后，该订单 $b$ 从订单簿中移除。如果 $CV_{b} = 0$（但 $V_{b} > 0$），则我们设置订单 $b$ 的当前量为 $CV_{b} = \min(V_{b}, TV_{b})$，设置 $PR_{b} =$ GP，并增加 GP。我们继续选择 $b$ 和生成交易的操作，直到 $V_{a} = 0$ 或者没有更多满足条件的订单 $b$ 在订单簿上。在后一种情况下，我们将订单 a 添加到订单簿中，$CV_{a} = \min(V_{a}, TV_{a})$ 和 $PR_{a} =$ GP，然后增加 GP。当订单 a 的匹配过程结束时，如果在同一对订单 a 和 $b$ 之间有多个交易（可能有很多！），它们都合并为一个交易，交易量等于各个交易量的总和。

如果 $T_{a} =$ BUY，我们寻找一个订单 $b$，使得 $T_{b} =$ SELL 且 $P_{b} \le P_{a}$，并在其中选择价格最小且优先级最小的订单 $b$。其余的匹配过程如上所述，交易的 BUY $ID_{t} = ID_{a},$ SELL $ID_{t} = ID_{b}, P_{t} = P_{b},$ 和 $V_{t} = \min(V_{a}, CV_{b})$。

最初订单簿是空的。你将看到几个订单，一个接一个地被交易所接收。你需要打印生成的交易以及所有订单处理完后的订单簿状态。

提示：优先级和 GP 在问题陈述中仅用于算法的形式描述。实际实现不必跟踪优先级。通常，交易所只需在其订单簿中保持每个价格的每种类型的订单的优先级排序列表。

Input Format

输入的第一行包含订单数量 $n (1 \le n \le 50 000)$。接下来的 $n$ 行中的每一行代表一个订单。每个订单由一个以空格分隔的五元组 ID $T P V$ TV 给出，其中 $1 \le$ ID $\le 1 000 000 , T = 1$ 表示 BUY，$T = 2$ 表示 SELL，$1 \le P \le 100 000$ 且 $1 \le$ TV $\le V \le 1 000 000 000$。

Output Format

对于每个订单，打印处理该订单生成的所有交易，按 (BUY ID, SELL ID) 对的升序排列，每个交易占一行。每个交易应打印为一个以空格分隔的四元组整数 BUY ID SELL ID $P V$。保证交易总数不超过 $100 000$。在所有交易之后打印一个空行，接着是订单簿。订单簿上仍然存在的每个订单应打印为一个以空格分隔的六元组 ID $T P V$ TV CV，首先按 $P$ 排序，然后按 PR 排序。

7
42 1 100 200 20
239 1 100 50 50
1111 1 101 30 15
1234 1 100 300 15
4321 2 99 125 25
5678 1 101 30 30
8765 2 101 100 20

42 4321 100 30
239 4321 100 50
1111 4321 101 30
1234 4321 100 15
5678 8765 101 30

42 1 100 170 20 10
1234 1 100 285 15 15
8765 2 101 70 20 20

Hint

时间限制：1 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。