E. Final Rankings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The championship director Artem is constantly improving the testing system, making it more stable, efficient, and user-friendly.

This time, Artem has upgraded the team sorting system in the results table. To test his modification, Artem decided to run it on the results of one of the previous championships.

However, a problem arose — Artem only has the log of submissions, but he does not have the final ranking of the teams.

Help Artem — based on the available information about the teams' submissions, calculate the final results and their rankings.

Rules for Sorting Teams and Determining Rankings

  • First, teams are sorted in descending order of the number of correctly solved problems.
  • In case of a tie in the number of solved problems, teams are sorted in ascending order of total penalty time:
    • Suppose a team correctly solved a problem after $$$M$$$ minutes from the start of the competition, having made exactly $$$F$$$ penalty attempts on that problem.
    • In this case, the team will receive $$$(M + 20 \cdot F)$$$ penalty time for solving this problem.
    • Subsequent attempts on an already solved problem do not change the penalty time.
    • If a problem is not solved, no penalty is incurred regardless of the number of attempts.
  • In case of a tie in both the number of solved problems and total penalty time, teams share the same rank.
    • For convenience, such teams are sorted in the table in ascending order of their identifiers.
Input

The first line contains two integers $$$n$$$ and $$$p$$$ $$$(1 \le n \le 10^3; 1 \le p \le 20)$$$ — the number of teams and the number of problems in the competition.

The second line contains an integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of submission records in the log.

In the $$$j$$$-th of the following $$$q$$$ lines, information about the $$$j$$$-th submission in the system is provided — four integers $$$M_j$$$, $$$ID_j$$$, $$$T_j$$$, and $$$V_j$$$ are given separated by spaces:

  • $$$M_j$$$ $$$(1 \le M_j \le 300)$$$ — the minute at which the submission was made;
  • $$$ID_j$$$ $$$(1 \le ID_j \le n)$$$ — the identifier of the team that made the submission;
  • $$$T_j$$$ $$$(1 \le T_j \le p)$$$ — the problem number for which the submission was made;
  • $$$V_j$$$ $$$(0 \le V_j \le 1)$$$ — the result of the submission testing ($$$1$$$ indicates success, $$$0$$$ indicates failure).

It is guaranteed that the submissions in the log are ordered chronologically, i.e., $$$M_j \le M_{j + 1}$$$ for all $$$1 \le j \lt q$$$.

This also means that even if $$$M_j = M_{j + 1}$$$, it should be considered that the $$$j$$$-th submission occurred before the $$$(j + 1)$$$-th.

Output

In the $$$i$$$-th of $$$n$$$ lines, output four integers $$$R_i$$$, $$$ID_i$$$, $$$S_i$$$, $$$X_i$$$ separated by spaces:

  • $$$R_i$$$ $$$(1 \le R_i \le n)$$$ — the final rank of the team on the $$$i$$$-th line of the table;
  • $$$ID_i$$$ $$$(1 \le ID_i \le n)$$$ — the identifier of the team;
  • $$$S_i$$$ $$$(0 \le S_i \le p)$$$ — the number of problems solved by the team;
  • $$$X_i$$$ $$$(0 \le X_i \le 10^9)$$$ — the total penalty time of the team.
Example
Input
5 3
23
15 1 1 0
30 2 2 0
30 1 1 1
43 3 1 0
43 2 1 1
65 3 1 0
80 3 2 0
87 3 1 1
99 2 2 1
99 5 2 0
100 1 2 0
100 4 1 0
130 1 2 0
130 5 2 1
130 2 3 0
135 5 2 0
140 5 3 1
199 2 3 0
200 4 3 0
200 1 2 1
280 4 2 0
290 2 3 0
299 2 3 1
Output
1 2 3 521
2 1 2 290
2 5 2 290
4 3 1 127
5 4 0 0
Note

First test example

A total of $$$5$$$ teams participated in the competition, and $$$3$$$ problems were available for solving.

  • Team $$$1$$$:
    • solved problem $$$1$$$ at time $$$30$$$, having made one penalty attempt before that — received $$$50$$$ minutes of penalty.
    • solved problem $$$3$$$ at time $$$200$$$, having made two penalty attempts before that — received $$$240$$$ minutes of penalty.
  • Team $$$2$$$:
    • solved problem $$$1$$$ at time $$$43$$$ with no penalty attempts — received $$$43$$$ minutes of penalty.
    • solved problem $$$2$$$ at time $$$99$$$ with one penalty attempt — received $$$119$$$ minutes of penalty.
    • solved problem $$$3$$$ at time $$$299$$$, having made three penalty attempts before that — received $$$359$$$ minutes of penalty.
  • Team $$$3$$$:
    • solved problem $$$1$$$ at time $$$87$$$ with two penalty attempts — received $$$127$$$ minutes of penalty.
    • made an incorrect attempt on problem $$$2$$$, but did not solve it — did not receive penalty time.
  • Team $$$4$$$:
    • made one incorrect attempt on each problem, but did not solve anything — did not receive penalty time.
  • Team $$$5$$$:
    • solved problem $$$2$$$ at time $$$130$$$, having made one penalty attempt before that — received $$$150$$$ minutes of penalty.
    • solved problem $$$3$$$ at time $$$140$$$ with no penalty attempts — received $$$140$$$ minutes of penalty.
    • made another attempt on problem $$$2$$$ after solving it — this did not affect its final rank in the table.

In total:

  • Team $$$2$$$ is in first place with $$$3$$$ solved problems and $$$521$$$ minutes of penalty.
  • Team $$$1$$$ is in second place with $$$2$$$ solved problems and $$$290$$$ minutes of penalty.
  • Team $$$5$$$ is in second place with $$$2$$$ solved problems and $$$290$$$ minutes of penalty.
  • Team $$$3$$$ is in fourth place with $$$1$$$ solved problem and $$$127$$$ minutes of penalty.
  • Team $$$4$$$ is in fifth place with $$$0$$$ solved problems and $$$0$$$ minutes of penalty.