J. Grand Prix of Ballance
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ballance is a classic game where players use the keyboard to control a ball through complex structures high above the ground, avoiding falls while solving puzzles to reach the end of each level. Recently, the player community has developed online mods and hosts regular online competitions, such as the Grand Prix of Ballance.

The Grand Prix consists of $$$n$$$ levels, numbered from $$$1$$$ to $$$n$$$, with $$$m$$$ participants, numbered from $$$1$$$ to $$$m$$$. The competition uses a point system: players earn points based on their ranking in each level, and the sum of their points across all levels determines the final standings. Each level has a designated start time, and participants must complete the level as quickly as possible. As a staff member, you receive a server log during the match containing three types of messages (it is guaranteed that $$$1\le x\le n$$$ and $$$1\le id\le m$$$):

  • 1 x — Type 1: the match on Level $$$x$$$ has started.
  • 2 id x — Type 2: participant indexed $$$id$$$ has completed Level $$$x$$$.
  • 3 id x — Type 3: participant indexed $$$id$$$ voluntarily gives up completing Level $$$x$$$.

A Type 1 message indicates the start of Level $$$x$$$ until a new Type 1 message appears for a different level. Only messages that correspond to the currently active level are considered valid; all messages for other levels should be ignored. Messages before the first Type 1 message are also ignored. Each level appears at most once in a Type 1 message.

Each player may yield multiple Type 2 and Type 3 messages per level, but only the first valid message counts. Specifically:

  • Messages are ignored if they do not match the active level indicated by the Type 1 message.
  • If a player's first valid message for a level is Type 2, they are considered to have completed the level successfully at that moment, and the player's any subsequent messages for that level are ignored.
  • If a player's first valid message for a level is Type 3, they are considered to have given up completing the level at that moment, and the player's any subsequent messages for that level are ignored.
  • If a player yields no messages for a level, they are considered not to have completed the level.

Points are awarded to participants who complete the level as follows: the first player to complete the level receives $$$m$$$ points, the second receives $$$m-1$$$ points, and so on. Participants who do not complete the level, including those who give up, receive no points.

Your task is to output the current total points of each participant in descending order based on the log. If multiple participants have the same points, they should be listed in ascending order by their index.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$), indicating the number of test cases.

For each test case, the first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n \leq 10^5$$$, $$$2 \leq m \leq 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$), indicating the number of levels, participants, and log messages, respectively.

The following $$$q$$$ lines contain the log messages as specified above. Of course, the messages are presented in chronological order. The log may not contain all levels, as you may receive it midway through the competition. You only need to process the current results.

It is guaranteed that the sum of $$$n$$$, the sum of $$$m$$$, and the sum of $$$q$$$ over all test cases do not exceed $$$5 \cdot 10^5$$$, respectively.

Output

For each test case, output $$$m$$$ lines, each containing two integers: $$$id$$$ and $$$x$$$, where $$$id$$$ is the participant's index and $$$x$$$ is their total points, sorted in descending order of points. If multiple participants have the same points, list them in ascending order by their index.

Example
Input
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
Output
2 4
1 3
3 0
4 0
1 7
2 4
3 0
4 0
2 4
1 3
3 0
4 0