P15081 [ICPC 2024 Chengdu R] Grand Prix of Ballance

Ballance 是一款经典游戏，玩家使用键盘控制一颗球在高空复杂的结构中穿行，避免坠落，同时解开谜题以抵达每个关卡的终点。最近，玩家社区开发了在线模组，并定期举办在线比赛，例如 Ballance 大奖赛。 大奖赛包含 $n$ 个关卡，编号从 $1$ 到 $n$，以及 $m$ 名参与者，编号从 $1$ 到 $m$。比赛采用积分制：玩家根据他们在每个关卡中的排名获得积分，他们在所有关卡中的积分总和决定了最终排名。每个关卡都有指定的开始时间，参与者必须尽快完成该关卡。作为工作人员，你在比赛期间收到一份服务器日志，其中包含三种类型的消息（保证 $1\le x\le n$ 且 $1\le id\le m$）： - $\tt{1\ x}$ —— 类型 1：第 $x$ 关的比赛开始。 - $\tt{2\ id\ x}$ —— 类型 2：编号为 $id$ 的参与者完成了第 $x$ 关。 - $\tt{3\ id\ x}$ —— 类型 3：编号为 $id$ 的参与者自愿放弃完成第 $x$ 关。 一条类型 1 的消息标志着第 $x$ 关的开始，直到出现针对另一关卡的新类型 1 消息为止。只有与当前活动关卡对应的消息才被视为有效；所有针对其他关卡的消息都应被忽略。第一条类型 1 消息之前的消息也一并忽略。每个关卡在类型 1 消息中最多出现一次。 每名玩家在每个关卡可能产生多条类型 2 和类型 3 消息，但只有第一条有效消息会被计入。具体规则如下： - 如果消息与类型 1 消息指示的活动关卡不匹配，则忽略该消息。 - 如果玩家对某关卡的第一条有效消息是类型 2，则认为他在该时刻成功完成了该关卡，并且该玩家针对该关卡的后续所有消息都将被忽略。 - 如果玩家对某关卡的第一条有效消息是类型 3，则认为他在该时刻放弃了完成该关卡，并且该玩家针对该关卡的后续所有消息都将被忽略。 - 如果玩家对某关卡没有产生任何消息，则认为他未完成该关卡。 完成关卡的参与者将按如下规则获得积分：第一个完成关卡的玩家获得 $m$ 分，第二个获得 $m-1$ 分，以此类推。未完成关卡的参与者（包括放弃者）不得分。 你的任务是根据日志输出每位参与者当前的总积分，并按积分降序排序。如果多名参与者积分相同，则按他们的编号升序列出。

- 第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示测试用例的数量。 - 对于每个测试用例，第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n \leq 10^5$，$2 \leq m \leq 10^5$，$1 \leq q \leq 2 \cdot 10^5$），分别表示关卡数、参与者人数和日志消息数。 - 接下来的 $q$ 行包含如上所述的日志消息。消息按时间顺序给出。日志可能不包含所有关卡，因为你可能是在比赛中途收到它的。你只需要处理当前的结果。 保证所有测试用例的 $n$ 之和、$m$ 之和以及 $q$ 之和分别不超过 $5 \cdot 10^5$。

对于每个测试用例，输出 $m$ 行，每行包含两个整数：$id$ 和 $x$，其中 $id$ 是参与者的编号，$x$ 是其总积分，按积分降序排序。如果多名参与者积分相同，则按编号升序列出。

翻译由 DeepSeek V3 完成