《Ballance》是一款经典游戏，玩家通过键盘控制球体在离地高处的复杂结构中穿行，在避开坠落的同时解开谜题，最终到达关卡终点。最近，玩家社区开发了在线模组并举办了定期的在线比赛，例如“《Ballance》大奖赛”。

大奖赛包含 $n$ 个关卡，编号为 $1$ 到 $n$，共有 $m$ 名参赛者，编号为 $1$ 到 $m$。比赛采用积分制：玩家根据在每个关卡中的排名获得积分，所有关卡积分的总和决定最终排名。每个关卡都有指定的开始时间，参赛者必须尽可能快地完成关卡。作为工作人员，你在比赛期间会收到一份包含三种类型消息的服务器日志（保证 $1 \le x \le n$ 且 $1 \le id \le m$）：

• 1 x — 类型 1：$x$ 号关卡的比赛已经开始。
• 2 id x — 类型 2：编号为 $id$ 的参赛者完成了 $x$ 号关卡。
• 3 id x — 类型 3：编号为 $id$ 的参赛者主动放弃完成 $x$ 号关卡。

类型 1 消息表示 $x$ 号关卡开始，直到出现另一个不同关卡的类型 1 消息为止。只有与当前活跃关卡对应的消息才被视为有效；其他关卡的消息应被忽略。在第一条类型 1 消息之前的消息也会被忽略。每个关卡在类型 1 消息中最多出现一次。

每位玩家在每个关卡中可能会产生多条类型 2 和类型 3 消息，但只有第一条有效消息计入统计。具体规则如下：

• 如果消息与类型 1 消息指示的当前活跃关卡不匹配，则忽略该消息。
• 如果玩家在某个关卡的第一条有效消息是类型 2，则视为该玩家在此时成功完成了该关卡，该玩家后续针对该关卡的任何消息都将被忽略。
• 如果玩家在某个关卡的第一条有效消息是类型 3，则视为该玩家在此时放弃了该关卡，该玩家后续针对该关卡的任何消息都将被忽略。
• 如果玩家对某个关卡没有产生任何消息，则视为未完成该关卡。

积分奖励规则如下：第一个完成关卡的玩家获得 $m$ 分，第二个获得 $m-1$ 分，以此类推。未完成关卡的参赛者（包括放弃者）得 $0$ 分。

你的任务是根据日志输出每位参赛者当前的积分总和，并按积分降序排列。如果多名参赛者积分相同，则按编号升序排列。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n$、$m$ 和 $q$ ($1 \le n \le 10^5, 2 \le m \le 10^5, 1 \le q \le 2 \cdot 10^5$)，分别表示关卡数、参赛者数和日志消息数。

接下来的 $q$ 行包含上述格式的日志消息。消息按时间顺序排列。日志可能不包含所有关卡，因为你可能是在比赛中途接收到的。你只需要处理当前的结果。

保证所有测试用例中 $n$ 的总和、$m$ 的总和以及 $q$ 的总和分别不超过 $5 \cdot 10^5$。

输出格式

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

样例

输入 1

3
3 4 6
1 2
2 1 1
2 2 2
3 3 2
2 3 2
2 1 2
3 4 8
1 2
2 1 1
2 2 2
3 3 2
2 3 2
2 1 2
1 1
2 1 1
3 4 7
1 2
2 1 1
2 2 2
3 3 2
2 3 2
2 1 2
1 1

输出 1

2 4
1 3
3 0
4 0
1 7
2 4
3 0
4 0
2 4
1 3
3 0
4 0