G. Dynamic Ranklist
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The organizers of a programming training camp are running a long practice contest. Initially, participant $$$i$$$ belongs to a team containing only $$$i$$$ for every $$$1 \le i \le N$$$. As the camp progresses, coaches may merge teams, and the live scoreboard must immediately reflect the new team standings.

There is one complication: verdict logs arrive from multiple judging servers. The events are processed in the order they are received, but a submission event contains its actual contest timestamp. Therefore, an accepted submission reported later may have happened earlier than submissions already processed.

You are given all events received by the scoreboard system. During the contest, two kinds of events may occur:

  • A submission verdict arrives.
  • Two existing teams merge into one team.

Submission verdicts are processed in the order they appear in the input. However, each submission also has a timestamp $$$t$$$, which is the actual contest time when the submission was made.

Whenever a team receives a new verdict or two teams merge, the team's score is recalculated using all submissions currently belonging to that team.

Scoring Rules

For each team:

  • The solve count is the number of distinct problems for which the team has at least one accepted verdict.
  • The total penalty is the sum of the penalties of all solved problems.

For one solved problem:

  • A team may have multiple accepted submissions for the same problem. Let $$$T$$$ be the minimum timestamp among all accepted submissions by the team for that problem.
  • Let $$$W$$$ be the number of wrong-answer submissions by the team for that problem with timestamp strictly less than $$$T$$$.
  • The problem penalty is $$$T + 20 \cdot W$$$.

Unsolved problems contribute $$$0$$$ penalty.

Ranking Rules

A team ranks strictly better than another team if, in order:

  1. It has a larger solve count.
  2. If solve counts are equal, it has a smaller total penalty.
  3. If both are equal, it has a smaller minimum participant ID among its members.

The rank of a team is $$$1 +$$$ the number of currently existing teams that rank strictly better than it.

Input

The first line contains one integer $$$T$$$ ($$$1 \le T \le 100000$$$), the number of test cases.

For each test case, the first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 100000$$$), where $$$N$$$ is the number of participants and $$$Q$$$ is the number of events.

Each of the next $$$Q$$$ lines describes one event.

For a type $$$1$$$ event, the format is 1 t u p v. Here:

  • $$$t$$$ is the chronological submission timestamp.
  • $$$u$$$ is the participant who made the submission. The submission belongs to the team containing $$$u$$$ at that moment.
  • $$$p$$$ is the problem ID.
  • $$$v$$$ is the verdict: $$$0$$$ means wrong answer, and $$$1$$$ means accepted.

For a type $$$2$$$ event, the format is 2 u v. The current teams containing participants $$$u$$$ and $$$v$$$ merge into a single team. If they are already in the same team, the operation does nothing.

It is guaranteed that:

  • $$$1 \le t \le 10^9$$$
  • $$$1 \le u, v \le N$$$
  • $$$1 \le p \le 100000$$$
  • Within one test case, all submission timestamps are distinct.
  • In one input file, the sum of all $$$N$$$ values is at most $$$100000$$$.
  • In one input file, the sum of all $$$Q$$$ values is at most $$$100000$$$.
Output

For each test case, output exactly $$$Q + N$$$ lines.

After each event, print three integers in the format Rank Solves Penalty.

  • For a type $$$1$$$ event, print the rank and score of the team containing participant $$$u$$$.
  • For a type $$$2$$$ event, print the rank and score of the team containing participants $$$u$$$ and $$$v$$$ after the merge. If they were already in the same team, print the current rank and score of that team.

After all events in the test case, print $$$N$$$ more lines. For each participant $$$i$$$ from $$$1$$$ to $$$N$$$, print one line in the format Rank Solves Penalty for the final team containing participant $$$i$$$.

Do not print blank lines between test cases.

Example
Input
1
3 5
1 100 1 1 0
1 150 2 1 1
2 1 2
2 2 1
1 50 1 1 1
Output
1 0 0
1 1 150
1 1 170
1 1 170
1 1 50
1 1 50
1 1 50
2 0 0
Note

Initially, participants $$$1$$$, $$$2$$$, and $$$3$$$ are in separate teams.

After the first event, participant $$$1$$$ has only one wrong answer on problem $$$1$$$, so the team has score $$$(0, 0)$$$.

After the second event, participant $$$2$$$ has one accepted submission on problem $$$1$$$ at timestamp $$$150$$$, so that team has score $$$(1, 150)$$$.

After the third event, the teams containing participants $$$1$$$ and $$$2$$$ merge. For problem $$$1$$$, the wrong answer at $$$100$$$ is before the accepted submission at $$$150$$$, so the penalty becomes $$$150 + 20 \cdot 1 = 170$$$.

The fourth event is a no-op merge because participants $$$2$$$ and $$$1$$$ are already in the same team, but the current rank and score must still be printed.

In the fifth event, participant $$$1$$$ receives an accepted verdict on problem $$$1$$$ at timestamp $$$50$$$. Although this event appears later in the input, timestamp $$$50$$$ is earlier than the previously seen submissions. Therefore, the earliest accepted timestamp becomes $$$50$$$, and the wrong answer at $$$100$$$ is no longer before the first accepted verdict. The penalty becomes $$$50$$$.